题解 P1313 【计算系数】

### 【问题描述】 给定一个多项式(ax + by)^k，请求出多项式展开后 x^n*y^m 项的系数。 ### 【输入数据】 共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。 ### 【输出数据】 输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取 模后的结果。 ### 【输入样例 1】 1 1 3 1 2 ### 【输出样例 1】 3 ### 【数据范围】 对于 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。 ------------ ------------ 这题可以用dp做 用dp[i][j]表示x的次数为i，y的次数为j时的系数 转移方程就是dp[i][j]=dp[i-1][j]×a + dp[i][j-1]×b 注意枚举时，要先枚举i+j，不能同时枚举i和j，要保证和相等 ```cpp #include<map> #include<set> #include<list> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int read() { int x=0,flag=0; char ch=getchar(); if(ch=='-') flag=1; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); if(flag) return -x; return x; } const int mod=10007; int a,b,k,n,m; int dp[1010][1010]; int main() { freopen("factor.in","r",stdin); freopen("factor.out","w",stdout); memset(dp,0,sizeof(dp)); a=read(),b=read(),k=read(),n=read(),m=read(); a%=mod,b%=mod; dp[1][0]=a,dp[0][1]=b; for(int s=2;s<=k;s++) for(int i=0;i<=s;i++) { int j=s-i; if(i>0) dp[i][j]+=dp[i-1][j]*a; dp[i][j]%=mod; if(j>0) dp[i][j]+=dp[i][j-1]*b; dp[i][j]%=mod; } cout<<dp[n][m]; fclose(stdin); fclose(stdout); return 0; } ```