2019西安联训B层 Day 5 test T2 排列组合
做法：组合数取模
其实我们观察那么长一个式子，其实它有一个结论，在数学竞赛中也常提到，结果就是C(2n,n),相当于从2n个数选n个数出来。因为阶乘的结果太大，所以我们还需要用到逆元。
对于逆元我也会写博客来讲解，求逆元有多种方法，扩欧，费马小定理+快速幂，递推打表，递归(会爆栈）
扩欧求逆元
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int maxn=1e7+7; int T,n; long long f[maxn]; long long ans; void init(){ f[0]=1; for(int i=1;i<=2000010;i++){ f[i]=f[i-1]*i%mod; } } long long Exgcd(long long a,long long &x,long long b,long long &y){ if(b==0){ x=1; y=0; return a; } long long GCD=Exgcd(b,x,a%b,y); long long tmp=x; x=y; y=tmp-(a/b)*y; return GCD; } long long inv(long long a,long long b){ long long x,y; if(Exgcd(a,x,b,y)!=1) return -1; else return (x%b+b)%b; } int main() { scanf("%d",&T); init(); while(T--){ scanf("%d",&n); printf("%lld ",f[2*n]*inv(f[n],mod)%mod*inv(f[n],mod)%mod); } return 0; }
快速幂求逆元
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int maxn=1e7+7; long long f[maxn]; void jc(){ f[0]=1; for(int i=1;i<=2000010;i++){ f[i]=f[i-1]*i%mod; } } long long ksm(long long a,long long b){ long long base=1; while(b){ if(b&1) base=base*a%mod; b>>=1; a=a*a%mod; } return base; } int T,n; int main() { scanf("%d",&T); jc(); while(T--){ scanf("%d",&n); printf("%lld ",f[2*n]*ksm(f[n],mod-2)%mod*ksm(f[n],mod-2)%mod); } return 0; }
结果