模板

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;