首页 > 代码库 > NOIP 2011 提高组 计算系数
NOIP 2011 提高组 计算系数
有二项式定理 `\left( a+b\right) ^{n}=\sum _{r=0}^{n}\left( \begin{matrix} n\\ r\end{matrix} \right) a^{n-r}b^{r}`。
组合数C(a,b)=C(a-1,b)+C(a-1,b-1)。
`n^2`递推即可。
然后快速幂计算`a^m`和`b^n`的值。
于是`C(k,n)*a^m*b^n`就是答案。
代码：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>//by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);LL a,b,k,n,m;LL c[1005][1005];LL pow(LL a,LL b){ LL ret=1; while(b){ if(b&1) ret=ret*a%10007; a=a*a%10007; b>>=1; } return ret;}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m); c[0][0]=1; for(int i=1;i<=k;i++){ c[i][0]=1; for(int j=1;j<=i;j++){ c[i][j]=(c[i-1][j]+c[i-1][j-1])%10007; } } printf("%lld\n",pow(a%10007,n)*pow(b%10007,m)%10007*c[k][n]%10007); return 0;}
NOIP 2011 提高组 计算系数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。