【国庆の礼物 之一】洛谷P1313 计算系数

链接
【国庆の礼物 之一】洛谷P1313 计算系数

分析:使用杨辉三角的系数,构造一个杨辉三角即可。然后乘上am和bn,注意数据范围和取模。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=10007,K=1010;

ll f[K][K];//存放杨辉三角的数组
ll a,b,k,n,m;

ll f1(ll a,ll b){
  ll ans=1;
  for(int i=1;i<=b;i++)ans*=a,ans%=MOD;
  return ans%MOD;
}
int main(){
  cin>>a>>b>>k>>n>>m;
  f[0][0]=1;
  for(int i=1;i<=k+1;i++){
    for(int j=1;j<=i;j++){
      f[i][j]=f[i-1][j]+f[i-1][j-1];//两数之和
      f[i][j]%=MOD;
      //printf("%3d",f[i][j]);
    }
    //printf("\n");
  }
  cout<<((f[k+1][m+1]%MOD) * (f1(a,n)%MOD))%MOD * (f1(b,m)%MOD)  % MOD<<endl;
}

/*

C(k,m)* a^n * b^m * x^n * y^m
*/
上一篇:动态规划算法二:最长公共子序列(LCS)


下一篇:Codechef MSTONES Milestones