题解 P1313 【计算系数】

2018-05-13 19:16:24


【问题描述】

给定一个多项式(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,要保证和相等

#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;
}