【转】TYVJ 1695 计算系数（NOIP2011 TG DAY2 1）

 计算系数

 题目描述

 给定一个多项式(ax + by)^k，请求出多项式展开后xⁿ y^m项的系数。

 【数据范围】

 对于 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。

 输入格式

 共一行，包含 5 个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。

 输出格式

 输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取

 模后的结果。

 输入输出样例】
factor.in        factor.out
1 1 3 1 2        3

 

下面是某网友的代码：

来源：http://blog.sina.com.cn/s/blog_78aa51270100vqaz.html

#01: Accepted (0ms, 4184KB)
#02: Accepted (0ms, 4184KB)
#03: Accepted (0ms, 4184KB)
#04: Accepted (0ms, 4184KB)
#05: Accepted (0ms, 4184KB)
#06: Accepted (0ms, 4184KB)
#07: Accepted (0ms, 4184KB)
#08: Accepted (0ms, 4184KB)
#09: Accepted (0ms, 4184KB)
#10: Accepted (0ms, 4184KB)

Accepted / 100 / 0ms / 4184KB

解题报告：简单的递推而已。注意取模的位置就好了。不解释了。

#include<stdio.h>
#define rep(i,n) for(i=1;i<=n;i++)
const int mo=10007;
int a,b,k,n,m,i,j;
int f[1010][1010];
int main(){
    //freopen("factor.in","r",stdin);
    //freopen("factor.out","w",stdout);
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    a%=mo;b%=mo;f[0][0]=1;
    rep(i,n) f[i][0]=(f[i-1][0]*a)%mo;
    rep(i,m) f[0][i]=(f[0][i-1]*b)%mo;
    rep(i,n) rep(j,m) f[i][j]=(f[i-1][j]*a + f[i][j-1]*b)%mo;
    printf("%d\n",f[n][m]);
    //system("pause");
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

 

----------------------------------另一网友的分析--------------------------------------------------------

http://blog.sina.com.cn/s/blog_606a23dd010128lo.html

这道题虽然出现在提高组，却并不一定只能用高中知识解决。
其实，这道题可以用递推解决。【个人感觉下面这段分析描述不是很对。可以直接跳过到最后面的分析。】
设f[i][j]为(ax+by)^i的x^j*y^(n-j)的系数。显然可以得到公式：

   f[i][j]=(f[i-1][j-1]*a+f[i-1][j]*b)007。
时间复杂度O（N^2）

#include<stdio.h>
#include<stdlib.h>
#define mod 10007
int a,b,n,m,k,i,j,f[1010][1010];
int main()
{
    scanf("%d %d %d %d %d",&a,&b,&k,&n,&m);
    a%=mod,b%=mod;
    f[1][0]=b,f[1][1]=a;
    for(i=2;i<=k;i++)
        for(j=0;j<=i&&j<=n;j++)
        {
            f[i][j]=f[i-1][j]*b%mod;
            if(j)
                f[i][j]=(f[i][j]+f[i-1][j-1]*a)%mod;
        }
    printf("%d\n",f[k][n]);
    return 0;
}

 

 

===================================================================================

下面是我自己的理解：

 

前面第一位的程序是对的，就是写代码的方式有些绕，而且分析少了一点。结合了第二位的分析，感觉第二位的分析描述没对。

假设f[i][j]表示（ax+by）^n的展开式中某一项x^i*y^j 的系数，其中i+j==n。

那么，x^i*y^j 可以由两种方案来递归构造：

（1）.   x^i*y^j= x^（i-1）*y^j*x

（2）.   x^i*y^j= x^i*y^(j-1)*y

把上面的x和y分别替换为ax和by，那就容易知道 f[i][j]=f[i-1][j]*a+f[i][j-1]*b

于是，我们可以构造一个二维数组f[][]来递推f[n][m]的值。递推的方法和上面第一个网友的代码一样。

第一个for是构造二维数组的第0列：

接着第二个for是构造二维数组的第0行：

接着用一个二重循环递推构造了整个二维数组,直至计算出f[n][m]的值。

最后即可直接输出f[n][m]。

 

还无法理解这个过程的可以自己用（ax+by）^2分析一下。

 

 

#include<stdio.h>
const int mo=10007;
int a,b,k,n,m,i,j;
int f[1010][1010];
int main()
    {
    freopen("factor.in","r",stdin);
    freopen("factor.out","w",stdout);
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    a%=mo;b%=mo;f[0][0]=1;
    for(i=1;i<=n;i++) f[i][0]=(f[i-1][0]*a)%mo;
    for(i=1;i<=m;i++) f[0][i]=(f[0][i-1]*b)%mo;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            f[i][j]=(f[i-1][j]*a + f[i][j-1]*b)%mo;
    }  
    printf("%d\n",f[n][m]);
    return 0;
}