【转】TYVJ 1695 计算系数(NOIP2011 TG DAY2 1)

时间:2022-09-03 14:37:42

计算系数

题目描述

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

输入格式

共一行,包含 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=;
int a,b,k,n,m,i,j;
int f[][];
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[][]=;
rep(i,n) f[i][]=(f[i-][]*a)%mo;
rep(i,m) f[][i]=(f[][i-]*b)%mo;
rep(i,n) rep(j,m) f[i][j]=(f[i-][j]*a + f[i][j-]*b)%mo;
printf("%d\n",f[n][m]);
//system("pause");
//fclose(stdin);
//fclose(stdout);
return ;
}

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

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[][];
int main()
{
scanf("%d %d %d %d %d",&a,&b,&k,&n,&m);
a%=mod,b%=mod;
f[][]=b,f[][]=a;
for(i=;i<=k;i++)
for(j=;j<=i&&j<=n;j++)
{
f[i][j]=f[i-][j]*b%mod;
if(j)
f[i][j]=(f[i][j]+f[i-][j-]*a)%mod;
}
printf("%d\n",f[k][n]);
return ;
}
 
===================================================================================
下面是我自己的理解:
 
前面第一位的程序是对的,就是写代码的方式有些绕,而且分析少了一点。结合了第二位的分析,感觉第二位的分析描述没对。
假设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列:
【转】TYVJ 1695 计算系数(NOIP2011 TG DAY2 1)
接着第二个for是构造二维数组的第0行:
【转】TYVJ 1695 计算系数(NOIP2011 TG DAY2 1)
接着用一个二重循环递推构造了整个二维数组,直至计算出f[n][m]的值。
最后即可直接输出f[n][m]。
 
还无法理解这个过程的可以自己用(ax+by)^2分析一下。
 
 #include<stdio.h>
const int mo=;
int a,b,k,n,m,i,j;
int f[][];
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[][]=;
for(i=;i<=n;i++) f[i][]=(f[i-][]*a)%mo;
for(i=;i<=m;i++) f[][i]=(f[][i-]*b)%mo;
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
f[i][j]=(f[i-][j]*a + f[i][j-]*b)%mo;
}
printf("%d\n",f[n][m]);
return ;
}
 
 
 
 
 
 

【转】TYVJ 1695 计算系数(NOIP2011 TG DAY2 1)的更多相关文章

  1. 计算系数&lpar;noip2011&rpar;

    [问题描述]给定一个多项式(ax + by)^k,请求出多项式展开后(x^n)*(y^m)项的系数.[输入]输入文件名为 factor.in.共一行,包含 5 个整数,分别为a,b,k,n,m,每两个 ...

  2. 计算系数&lpar;NOIP2011提高LuoguP1313&rpar;

    一道数论好题,知识点涉及扩展欧几里得,快速幂,逆元,二项式定理,模运算,组合数等. (别问为啥打了快速幂不用费马小求逆元...我就练习下扩欧) (数据就应该再加大些卡掉n^2递推求组合数的) #inc ...

  3. NOIP2011 day2 第一题 计算系数

    计算系数 NOIP2011 day2 第一题 描述 给定一个多项式(ax+by)^k,请求出多项式展开后x^n*y^m项的系数. 输入格式 共一行,包含5 个整数,分别为 a ,b ,k ,n ,m, ...

  4. 洛谷P1313 &lbrack;NOIP2011提高组Day2T1&rsqb;计算系数

    P1313 计算系数 题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数. 输入输出格式 输入格式: 输入文件名为factor.in. 共一行,包含5 个整数,分别 ...

  5. 一本通1648【例 1】「NOIP2011」计算系数

    1648: [例 1]「NOIP2011」计算系数 时间限制: 1000 ms         内存限制: 524288 KB [题目描述] 给定一个多项式 (ax+by)k ,请求出多项式展开后 x ...

  6. 题解 【NOIP2011】计算系数

    [NOIP2011]计算系数 Description 给定一个多项式 (ax+by)^k ,请求出多项式展开后 x^n * y^m 项的系数. Input 共一行,包含 5 个整数,分别为 a,b,k ...

  7. NOIP2011 计算系数

    1计算系数 给定一个多项式 (ax + by)k ,请求出多项式展开后 x n y m 项的系数. [输入] 输入文件名为 factor.in. 共一行,包含 5 个整数,分别为 a,b,k,n,m, ...

  8. luoguP1313 计算系数 题解&lpar;NOIP2011&rpar;

    P1313 计算系数 题目 #include<iostream> #include<cstdlib> #include<cstdio> #include<cm ...

  9. 【NOIP2011提高组】计算系数

    计算系数 算法:真·滚动数组模拟!!! 马上CSP/S了,这是远在今年暑假前的一天的校内考试题中的一道.当时做的时候不会组合数,不会二项式定理,不会DP,不会……只知道应该n*n的空间存一个杨辉三角形 ...

随机推荐

  1. 将文件从一台linux机器拷贝到多台的方法

    首先你所操作的各台linux机器间必须设置了ssh免密码登录,具体方法可上网查看.将文件从一台linux机器拷贝到多台分为以下几个步骤: 第一步:创建脚本文件remotecopy.sh #!/bin/ ...

  2. PAT1013

    #include<cstdio>#include<cstring>#include<vector>using namespace std;const int max ...

  3. LeetCode3 Longest Substring Without Repeating Characters

    题意: Given a string, find the length of the longest substring without repeating characters. Examples: ...

  4. ios 从前台返回到回台 从后台返回到前台 或者 支付宝支付订单后 对界面进行操作

    正常情况下,在AppDelegate中实现下面两个方法,能够监听从后台恢复到前台 - (void)applicationDidEnterBackground:(UIApplication *)appl ...

  5. 《Windows编程循序渐进》——MFC封装机制详解

    单文档

  6. 用php&plus;mysql&plus;ajax实现淘宝客服或阿里旺旺聊天功能 之 后台页面

    在上一篇随笔中,我们已经看了如何实现前台的对话功能:前台我限定了店主只有一人,店铺只有一个,所有比较单一,但后台就不一样了,而后台更像是我们常见的聊天软件:当然,前台也应该实现这种效果,但原理懂了,可 ...

  7. nginx做80端口转发

    server { server_name zjrzb.cn listen 80; location / { proxy_pass http://127.0.0.1:8090; proxy_set_he ...

  8. 使用themeleaf页面技术时,在JavaScript代码中使用for循环报错&period;&period;&period;&period;&period;

    解决方法: 在for循环前加上/* <![CDATA[ */,在for循环后加/* ]]> */,这样就能正常解析了:如下 /* <![CDATA[ */ for (var i = ...

  9. Redhat 用代理连外网

    设置 /etc/yum.conf 添加proxy=http://web-proxy.corp.xx.com:8080 /etc/yum.repos.d/rhel-source.repo 里面改成ena ...

  10. BZOJ3786星系探索——非旋转treap&lpar;平衡树动态维护dfs序&rpar;

    题目描述 物理学家小C的研究正遇到某个瓶颈. 他正在研究的是一个星系,这个星系中有n个星球,其中有一个主星球(方便起见我们默认其为1号星球),其余的所有星球均有且仅有一个依赖星球.主星球没有依赖星球. ...