组合数学

 1 typedef long long ll;
 2 
 3 const ll MOD = 1e9 + 7;     //  必须为质数才管用
 4 const ll MAXN = 1e5 + 3;
 5 
 6 ll fac[MAXN];       //  阶乘
 7 ll inv[MAXN];       //  阶乘的逆元
 8 
 9 ll QPow(ll x, ll n)
10 {
11     ll ret = 1;
12     ll tmp = x % MOD;
13 
14     while (n)
15     {
16         if (n & 1)
17         {
18             ret = (ret * tmp) % MOD;
19         }
20         tmp = tmp * tmp % MOD;
21         n >>= 1;
22     }
23 
24     return ret;
25 }
26 
27 void init()
28 {
29     fac[0] = 1;
30     for (int i = 1; i < MAXN; i++)
31     {
32         fac[i] = fac[i - 1] * i % MOD;
33     }
34     inv[MAXN - 1] = QPow(fac[MAXN - 1], MOD - 2);
35     for (int i = MAXN - 2; i >= 0; i--)
36     {
37         inv[i] = inv[i + 1] * (i + 1) % MOD;
38     }
39 }
40 
41 ll C(ll a, ll b)
42 {
43     if (b > a)
44     {
45         return 0;
46     }
47     if (b == 0)
48     {
49         return 1;
50     }
51     return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
52 }