逆元+快速幂+阶乘求组合数

直接暴力打表求法O(n*m)：

1
2
3
4
5
for(int i=0;i<=n;i++){
	c[i][0]=c[i][i]=1;
	for(int j=1;j<i;j++)
		c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

由于求组合数有阶乘的方法进行求解，但由于除法实际上是没办法使用直接进行取模的，因此实际上就需要进行逆元结合快速幂并且利用阶乘进行组合数的求解。

逆元其实和倒数差不都。

根据费马小定理，就可以得到a的逆元就是\(a^{(p-2)}\),于是就需要用到快速幂了

于是这个公式\(C(n,m)=n!*inv[m!]inv[(n-m)!]\)，其中inv表示逆元。

那么阶乘逆元要怎么经计算，由于\(inv[(n-1)!]=inv[n]*n\)

因此可以直接进行个递推，完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
const ll mod=998244353;
ll inv[maxn], fac[maxn];  //分别表示逆元和阶乘
//快速幂
ll quickPow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1)
            ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

void init(){
    //求阶乘
    fac[0]=1;
    for(int i=1;i<maxn;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    //求逆元
    inv[maxn-1]=quickPow(fac[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--)
    {
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}
ll C(int n,int m){
    if(m>n){
        return 0;
    }
    if(m==0)
        return 1;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
    init();
    int n,m;
    cin>>n>>m;
    cout<<C(n,m);
}


Grid 2

题面翻译

给一个 \(H\times W\) 的网格，每一步只能向右或向下走，给出 \(N\) 个坐标 \((r_1,c_1),(r_2,c_2),...,(r_n,c_n)\)，这些坐标对应的位置不能经过，求从左上角 \((1,1)\) 走到右下角 \((H,W)\) 的方案数，答案对 \(10^9+7\) 取模。

题目描述

縦 $ H $ 行、横 $ W $ 列のグリッドがあります。 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i, j) $ で表します。

グリッドのうち、$ N $ 個のマス $ (r_1, c_1), (r_2, c_2), , (r_N, c_N) $ は壁のマスであり、それら以外のマスはすべて空マスです。 マス $ (1, 1) $ および $ (H, W) $ は空マスであることが保証されています。

太郎君は、マス $ (1, 1) $ から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス $ (H, W) $ まで辿り着こうとしています。

マス $ (1, 1) $ から $ (H, W) $ までの太郎君の経路は何通りでしょうか？ $ 10^9 + 7 $ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ H $ $ W $ $ N $ $ r_1 $ $ c_1 $ $ r_2 $ $ c_2 $ $ : $ $ r_N $ $ c_N $

输出格式

マス $ (1, 1) $ から $ (H, W) $ までの太郎君の経路は何通りか？ $ 10^9 + 7 $ で割った余りを出力せよ。

样例 #1

样例输入 #1

1
2
3
3 4 2
2 2
1 4

样例输出 #1

1
3

样例 #2

样例输入 #2

1
2
3
5 2 2
2 1
4 2

样例输出 #2

1
0

样例 #3

样例输入 #3

1
2
3
4
5
5 5 4
3 1
3 5
1 3
5 3

样例输出 #3

1
24

样例 #4

样例输入 #4

1
2
100000 100000 1
50000 50000

样例输出 #4

1
123445622

提示

制約

  • 入力はすべて整数である。
  • $ 2  H, W  10^5 $
  • $ 1  N  3000 $
  • $ 1  r_i  H $
  • $ 1  c_i  W $
  • マス $ (r_i, c_i) $ はすべて相異なる。
  • マス $ (1, 1) $ および $ (H, W) $ は空マスである。

Sample Explanation 1

経路は次図の $ 3 $ 通りです。 ![](https://img.atcoder.jp/dp/grid_1_0_muffet.png)

Sample Explanation 2

経路が存在しない場合もあります。

Sample Explanation 4

答えを $ 10^9 + 7 $ で割った余りを出力することを忘れずに。

考虑看一道结合组合数和乘法逆元和阶乘的Dp好题。

首先组合数的求解部分和上述基本一致。

主要是Dp的过程比较抽象。

直接计算组合不好计算，思考计算出最终没有障碍的，减去第一个经过该障碍的

定义\(f_i\)表示从\((1,1)\)开始走，途中不经过任何一个障碍物到达第i个障碍，因此就可以考虑容斥。

\(f_i\) 就为 \((1,1)\rightarrow(r_i,c_i)\) 的所有方案数减去途中经过障碍物的方案数。

\((1,1)\rightarrow(r_i,c_i)\) 的所有方案数就为 \(C_{r_i+c_i-2}^{r_i-1}\)（一共要走 \(r_i+c_i-2\) 步，选择 \(r_i-1\) 步向下走）。

求经过障碍物的方案数，考虑枚举经过的第一个障碍物 \(j\)，方案数就为 \((1,1)\) 到 \((r_j,c_j)\) 不经过障碍物的方案数乘从这个障碍物到第 \(i\) 个障碍物的所有方案数，减去的总方案数就为 \(\sum f_j\times C_{r_i-r_j+c_i-r_j}^{r_i-r_j}(r_j\le r_i,c_j\le c_i)\)。(中间就是从这个1障碍物走到下一个障碍物的过程）

状态转移方程就为 \(f_i=C_{r_i+c_i-2}^{r_i-1}-\sum f_j\times C_{r_i-r_j+c_i-c_j}^{r_i-r_j}(r_j\le r_i,c_j\le c_i)\)。（这里是需要排序的，并且需要特判第二维坐标的大小，因为实际上是只能向下或者向右走的）

答案就为 \(f_{N+1}\)。（因为将最后终点设置为第一个障碍物了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e6+100;
const int M=1e6+100;
int fact[M];
int ifact[M];
int n,m,s,f[N];
int V;
pair<int,int>a[N];
int C(int x,int y) 
{
	return 1ll*fact[x]*ifact[x-y]%mod*ifact[y]%mod;
}
//组合数求解
int ksm(int a,int b=mod-2)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
        ans=1ll*ans*a%mod;
        }
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
//快速幂求解逆元
int solve(int x,int y) 
{
	return C(x+y,y);
}
signed main()
{
    cin>>n>>m>>s;
    V=n+m-2;
    for(int i=0;i<s;i++)
    {
        cin>>a[i].first>>a[i].second;
    }
    fact[0]=1;
    for(int i=1;i<=V;i++)
    {
        fact[i]=1ll*fact[i-1]*i%mod;
    }
    //求解阶乘
    ifact[V]=ksm(fact[V]);
    //求解逆元
    for(int i=V;i;i--)
    {
ifact[i-1]=1ll*ifact[i]*i%mod;
    }
    sort(a,a+s);
    a[s]={n,m};
    for(int i=0;i<=s;i++)
    {
    f[i]=solve(a[i].first-1,a[i].second-1);
    for(int j=0;j<i;j++)
    {
        if(a[j].second>a[i].second)
        {
        continue;
        }
        f[i]=(f[i]-1ll*f[j]*solve(a[i].first-a[j].first,a[i].second-a[j].second)%mod+mod)%mod;
    }
    }
cout<<f[s];
return 0;
}