计算系数 2011day2 t1
时间限制: 1 s 空间限制: 128000 KB
题目描述 Description
给定一个多项式(ax + by)^k,请求出多项式展开后x^n y^m项的系数。
输入描述 Input Description
共一行,包含 5 个整数,分别为a,b,k,n,m,每两个整数之间用一个空格隔开。
输出描述 Output Description
输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对10007 取模后的结果。
样例输入 Sample Input
1 1 3 1 2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
数据范围
对于 30%的数据,有0≤k≤10;
对于 50%的数据,有a = 1,b = 1;
对于 100%的数据,有0≤k≤1,000,0≤n, m≤k,且n + m = k,0≤a,b≤1,000,000。
#include<cstdio> #define M 10007 int ka[1100][1100]={0}; int sum; int a,b,k,n,m; long long ksm(int y,int k) { long long ans=1; while (k>0) { if (k%2) ans=ans*y%M; y=y*y%M; k/=2; } return ans; } int main() { scanf("%d%d%d%d%d",&a,&b,&k,&n,&m); a%=M; b%=M; ka[1][0]=ka[1][1]=1; for (int i=1;i<=k;i++) ka[i][0]=1; for (int i=2;i<=k;i++) for (int j=1;j<=i;j++) ka[i][j]=(ka[i-1][j-1]+ka[i-1][j])%M; if (a==1&&b==1) printf("%d",ka[k][m]); else { sum=(ksm(a,n)*ksm(b,m))%M*ka[k][m]%M; printf("%d",sum); } return 0; }
#include<cstdio> #define M 10007 #define N 1100 int ki[N][N]={0}; int a,b,k,n,m; int main() { scanf("%d%d%d%d%d",&a,&b,&k,&n,&m); a%=M; b%=M; ki[1][0]=a; ki[1][1]=b; for (int i=2;i<=k;i++) for (int j=0;j<=i&&j<=m;j++) { ki[i][j]=ki[i-1][j]*a%M; if (j) ki[i][j]=(k[i][j]+ki[i-1][j-1]*b)%M; } printf("%d",ki[k][m]); return 0; }