洛谷 P1313 计算系数
JDOJ 1747: [NOIP2011]计算系数 D2 T1
Description
给定一个多项式(ax + by)k，请求出多项式展开后xn ym项的系数。
Input
共一行，包含 5 个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。
Output
输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果。
Sample Input
1 1 3 1 2
Sample Output
3
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。
Source
题解：
此题有两种做法（可能有很多种，但我只会两种）：第一种是杨辉三角，第二种是递推。
先来讲一下递推：
设置状态\(dp[i][j]\)表示\(x^iy^j\)项的系数，显然答案就是\(dp[n][m]\)。初值\(dp[0][0]=1\)。
那么我们怎么设置状态转移方程呢？
很容易，我们在草纸上手推，\(dp[i-1][j]\)表示\(x^{i-1}y^j\)的系数，那么\(x^iy^j\)的系数显然就是这个东西再乘上一个\(ax\)。那么对其系数的贡献就是多乘上了一个\(a\)。
那么状态转移方程就是：
\[dp[i][j]=dp[i-1][j]\times a+dp[i][j-1]\times b
\]
\]
这里要注意，我们递推的时候是从\(0\)开始的，为了取模需要，我们将每次递推之前的\(dp[i][j]\)置成了\(0\).（这是有必要的，否则你要是用\(+=\)就没办法取模）。记得开\(long long\)。
代码如下：
#include<cstdio>
#define int long long
using namespace std;
const int maxk=1e3+10;
const int mod=10007;
int a,b,k,n,m;
int dp[maxk][maxk];
signed main()
{
scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);
dp[0][0]=1;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(!i && !j)
continue;
dp[i][j]=0;
if(i)
dp[i][j]=(dp[i][j]+dp[i-1][j]*a)%mod;
if(j)
dp[i][j]=(dp[i][j]+dp[i][j-1]*b)%mod;
}
printf("%lld",dp[n][m]);
return 0;
}