大数组合数取模(逆元+打表)

2019-04-13 15:47发布

站内文章 / 模拟电子
15831 0 1477
这里写图片描述
将阶乘O(n)打表之后C(n,m)便可O(1)求出，除法取模用逆元解决
hdu5698瞬间移动 #include using namespace std; const int maxn=200000; const int p=1000000007; int f[maxn+10]; void init(){//阶乘 f[0]=1; for(int i=1;i<=maxn;i++){ f[i]=(long long)f[i-1]*i%p; } } int fast(int a,int n){ if(n==0)return 1; if(n%2)return (long long)a*fast(a,n-1)%p; int tmp=fast(a,n/2); return (long long)tmp*tmp%p; } int C(int n,int m){ if(n==m||m==0)return 1; return ((long long)f[n]*fast(f[m],p-2)%p)*fast(f[n-m],p-2)%p; } int main(){ init(); int n,m; while(~scanf("%d%d",&n,&m)){ printf("%d ",C(n+m-4,m-2)); } return 0; }

热门文章