杨辉的行积
前置知识
- 杨辉三角形与组合数的关系
- 线性求逆元
分析
杨辉三角形的第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。
其实就是先预处理(预处理阶乘和逆元的阶乘),然后O(1)求组合数再乘起来取模即可参考代码
#include<bits/stdc++.h> using namespace std; const int N=1e6+1,mod=1e9+7; unsigned int C[N],g[N]; int main(){ int n,ans=1; scanf("%d",&n); C[0]=g[0]=g[1]=1; for(int i=2;i<n/2+1;++i)g[i]=(1ULL*g[mod%i]*(mod-mod/i))%mod; for(int i=1;i<=n/2+1;++i)C[i]=(1ULL*((1ULL*C[i-1]*(n-i))%mod)*g[i])%mod; for(unsigned int i=1;i<=n/2;++i)ans=(1ULL*ans*C[i-1])%mod; ans=1ULL*ans*ans%mod; if(n&1) ans=1ULL*ans*C[n/2]%mod; printf("%d",ans); return 0; }
```