洛谷 P1313 计算系数

洛谷传送门

JDOJ 1747: [NOIP2011]计算系数 D2 T1

JDOJ传送门

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

NOIP2011提高组

题解:

此题有两种做法(可能有很多种,但我只会两种):第一种是杨辉三角,第二种是递推。

先来讲一下递推:

设置状态\(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;
}
12-30 22:46