NOIP2011提高組 Day2 計算係數 factor 解題報告

題目查看、下載

【題目分析】
數論，C(k,m)*a^n*b^m即可。C(k,m)表示組合數，可以使用楊輝三角遞推求出。
考察知識點：
1) 二項式定理
2) 組合數遞推/楊輝三角
3) 同餘定理


【我的代碼】

#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int A,B,K,N,M;
const int MOD=10007;
int YH[1020][1020];
void yanghui()
{
 for (int i=0;i<=K+1;i++)
  for (int j=1;j<=K+2;j++)
   YH[i][j]=0;
 for (int i=0;i<=K+1;i++)
  YH[i][1]=1;
 for (int i=1;i<=K;i++)
 {
  for (int j=2;j<=i+1;j++)
  {
   YH[i][j]=(YH[i-1][j-1]+YH[i-1][j])%MOD;
  }
 }  
 
 /*
 for (int i=0;i<=K;i++)
 {
  for (int j=1;j<=i+1;j++)
   printf("%d ",YH[i][j]);
  printf("\n");
 }
 */
}
 
int Get(int num,int index)
{
 int res=1;
 for (int i=1;i<=index;i++)
  res=(res*num)%MOD;
 return res;
}
 
int main()
{
 freopen("factor.in","r",stdin);
 freopen("factor.out","w",stdout);
 scanf("%d %d %d %d %d\n",&A,&B,&K,&N,&M);
 yanghui();
 int NM=Get(A%MOD,N);
 int MM=Get(B%MOD,M);
 int res=(NM*MM)%MOD;
 res=(res*YH[K][M+1])%MOD;
 //printf("%d %d\n",NM,MM);
 printf("%d\n",res);
 return 0;
}