Combinatorial number formula
> but can be multiplied by the inverse element.
1 #include <cstdio>
2 #define ll long long
3 const ll maxn=1e9+7;
4 int n,m,K;
5 ll ans,fac[900005],inv[900005];
6 ll C(int n,int m) // n>=m
7 {
8 return fac[n]*inv[m]%maxn*inv[n-m]%maxn;
9 }
10 ll ksm(int a,int b)
11 {
12 ll s=1;
13 while (b)
14 {
15 if (b&1) s=s*a%maxn;
16 a=1ll*a*a%maxn;
17 b>>=1;
18 }
19 return s;
20 }
21 int main()
22 {
23 int i,j;
24 scanf("%d%d",&n,&m);
25 for (fac[0]=inv[0]=i=1;i<900005;i++) fac[i]=fac[i-1]*i%maxn;
26 inv[900004]=ksm(fac[900004],maxn-2);
27 for (i=900004;i>=1;i--) inv[i]=inv[i+1]*(i+1)%maxn;
28 printf("%lld\n",C(n,m));
29 return 0;
30 }
Post Views: 2