计算较大组合数模板

发表于 |
字数统计: 134 | 阅读时长 ≈ 1

取模P、P为素数（费马小定理）
逆元参考博客：https://www.zybuluo.com/ArrowLLL/note/713749

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int mod = 1e9 + 7;
const int maxn = 1e5 + 7;
typedef long long ll;  
ll fac[maxn];  
ll qpow(ll a,ll b)  
{  
    ll ans = 1;a %= mod;  
    for(ll i = b;i;i >>= 1,a = a * a % mod)  
        if(i & 1)ans = ans * a % mod;  
    return ans;  
}  
ll C(ll n,ll m)  
{  
    if(m > n || m < 0)return 0;  
    ll s1 = fac[n],s2 = fac[n - m] * fac[m] % mod;  
    return s1 * qpow(s2,mod - 2) % mod;  
}  
//主函数里：  
fac[0]=1;  
    for(int i = 1; i < maxn; i++)  
        fac[i]=fac[i - 1] * i % mod;