【转】TYVJ 1695 计算系数（NOIP2011 TG DAY2 1）-阿里云开发者社区

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

2014-11-01 728

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 计算系数题目描述给定一个多项式(ax + by)k，请求出多项式展开后xn ym项的系数。【数据范围】对于 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。

计算系数

题目描述

给定一个多项式(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

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

 1 #include<stdio.h>
 2 #define rep(i,n) for(i=1;i<=n;i++)
 3 const int mo=10007;
 4 int a,b,k,n,m,i,j;
 5 int f[1010][1010];
 6 int main(){
 7     //freopen("factor.in","r",stdin);
 8     //freopen("factor.out","w",stdout);
 9     scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
10     a%=mo;b%=mo;f[0][0]=1;
11     rep(i,n) f[i][0]=(f[i-1][0]*a)%mo;
12     rep(i,m) f[0][i]=(f[0][i-1]*b)%mo;
13     rep(i,n) rep(j,m) f[i][j]=(f[i-1][j]*a + f[i][j-1]*b)%mo;
14     printf("%d\n",f[n][m]);
15     //system("pause");
16     //fclose(stdin);
17     //fclose(stdout);
18     return 0;
19 }

View Code

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

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）

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define mod 10007
 4 int a,b,n,m,k,i,j,f[1010][1010];
 5 int main()
 6 {
 7     scanf("%d %d %d %d %d",&a,&b,&k,&n,&m);
 8     a%=mod,b%=mod;
 9     f[1][0]=b,f[1][1]=a;
10     for(i=2;i<=k;i++)
11         for(j=0;j<=i&&j<=n;j++)
12         {
13             f[i][j]=f[i-1][j]*b%mod;
14             if(j)
15                 f[i][j]=(f[i][j]+f[i-1][j-1]*a)%mod;
16         }
17     printf("%d\n",f[k][n]);
18     return 0;
19 }

View Code

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

下面是我自己的理解：

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

假设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分析一下。

 1 #include<stdio.h>
 2 const int mo=10007;
 3 int a,b,k,n,m,i,j;
 4 int f[1010][1010];
 5 int main()
 6     {
 7     freopen("factor.in","r",stdin);
 8     freopen("factor.out","w",stdout);
 9     scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
10     a%=mo;b%=mo;f[0][0]=1;
11     for(i=1;i<=n;i++) f[i][0]=(f[i-1][0]*a)%mo;
12     for(i=1;i<=m;i++) f[0][i]=(f[0][i-1]*b)%mo;
13     for(i=1;i<=n;i++)
14     {
15         for(j=1;j<=m;j++)
16             f[i][j]=(f[i-1][j]*a + f[i][j-1]*b)%mo;
17     }  
18     printf("%d\n",f[n][m]);
19     return 0;
20 }

View Code

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

热门文章

最新文章

相关电子书

相关实验场景