组合数

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 typedef long long LL;
 6 const int MAXN=200010;
 7 const int MOD=(int)1e9+7;
 8 int F[MAXN],Finv[MAXN],inv[MAXN];   //F是阶乘,Finv是逆元的阶乘
 9 
10 void init()
11 {
12     inv[1]=1;
13     for (int i=2;i<MAXN;i++) inv[i]=(MOD-MOD/i)*(LL)1*inv[MOD%i]%MOD;
14     F[0]=Finv[0]=1;
15     for (int i=1;i<MAXN;i++)
16     {
17         F[i]=F[i-1]*(LL)1*i%MOD;
18         Finv[i]=Finv[i-1]*(LL)1*inv[i]%MOD;
19     }
20     return;
21 }
22 int comb(int n,int m)   //comb(n, m)就是C(n, m)
23 {
24     if (m<0 || m>n) return 0;
25     return F[n]*(LL)1*Finv[n-m]%MOD*Finv[m]%MOD;
26 }
27 int main()
28 {
29     init();
30     return 0;
31 }

 

上一篇:动态规划——删除并获得点数(Leetcode 740)


下一篇:差分约束