计算系数
题目描述
给定一个多项式(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 ;
}
#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)的更多相关文章
-
计算系数(noip2011)
[问题描述]给定一个多项式(ax + by)^k,请求出多项式展开后(x^n)*(y^m)项的系数.[输入]输入文件名为 factor.in.共一行,包含 5 个整数,分别为a,b,k,n,m,每两个 ...
-
计算系数(NOIP2011提高LuoguP1313)
一道数论好题,知识点涉及扩展欧几里得,快速幂,逆元,二项式定理,模运算,组合数等. (别问为啥打了快速幂不用费马小求逆元...我就练习下扩欧) (数据就应该再加大些卡掉n^2递推求组合数的) #inc ...
-
NOIP2011 day2 第一题 计算系数
计算系数 NOIP2011 day2 第一题 描述 给定一个多项式(ax+by)^k,请求出多项式展开后x^n*y^m项的系数. 输入格式 共一行,包含5 个整数,分别为 a ,b ,k ,n ,m, ...
-
洛谷P1313 [NOIP2011提高组Day2T1]计算系数
P1313 计算系数 题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数. 输入输出格式 输入格式: 输入文件名为factor.in. 共一行,包含5 个整数,分别 ...
-
一本通1648【例 1】「NOIP2011」计算系数
1648: [例 1]「NOIP2011」计算系数 时间限制: 1000 ms 内存限制: 524288 KB [题目描述] 给定一个多项式 (ax+by)k ,请求出多项式展开后 x ...
-
题解 【NOIP2011】计算系数
[NOIP2011]计算系数 Description 给定一个多项式 (ax+by)^k ,请求出多项式展开后 x^n * y^m 项的系数. Input 共一行,包含 5 个整数,分别为 a,b,k ...
-
NOIP2011 计算系数
1计算系数 给定一个多项式 (ax + by)k ,请求出多项式展开后 x n y m 项的系数. [输入] 输入文件名为 factor.in. 共一行,包含 5 个整数,分别为 a,b,k,n,m, ...
-
luoguP1313 计算系数 题解(NOIP2011)
P1313 计算系数 题目 #include<iostream> #include<cstdlib> #include<cstdio> #include<cm ...
-
【NOIP2011提高组】计算系数
计算系数 算法:真·滚动数组模拟!!! 马上CSP/S了,这是远在今年暑假前的一天的校内考试题中的一道.当时做的时候不会组合数,不会二项式定理,不会DP,不会……只知道应该n*n的空间存一个杨辉三角形 ...
随机推荐
-
将文件从一台linux机器拷贝到多台的方法
首先你所操作的各台linux机器间必须设置了ssh免密码登录,具体方法可上网查看.将文件从一台linux机器拷贝到多台分为以下几个步骤: 第一步:创建脚本文件remotecopy.sh #!/bin/ ...
-
PAT1013
#include<cstdio>#include<cstring>#include<vector>using namespace std;const int max ...
-
LeetCode3 Longest Substring Without Repeating Characters
题意: Given a string, find the length of the longest substring without repeating characters. Examples: ...
-
ios 从前台返回到回台 从后台返回到前台 或者 支付宝支付订单后 对界面进行操作
正常情况下,在AppDelegate中实现下面两个方法,能够监听从后台恢复到前台 - (void)applicationDidEnterBackground:(UIApplication *)appl ...
-
《Windows编程循序渐进》——MFC封装机制详解
单文档
-
用php+mysql+ajax实现淘宝客服或阿里旺旺聊天功能 之 后台页面
在上一篇随笔中,我们已经看了如何实现前台的对话功能:前台我限定了店主只有一人,店铺只有一个,所有比较单一,但后台就不一样了,而后台更像是我们常见的聊天软件:当然,前台也应该实现这种效果,但原理懂了,可 ...
-
nginx做80端口转发
server { server_name zjrzb.cn listen 80; location / { proxy_pass http://127.0.0.1:8090; proxy_set_he ...
-
使用themeleaf页面技术时,在JavaScript代码中使用for循环报错.....
解决方法: 在for循环前加上/* <![CDATA[ */,在for循环后加/* ]]> */,这样就能正常解析了:如下 /* <![CDATA[ */ for (var i = ...
-
Redhat 用代理连外网
设置 /etc/yum.conf 添加proxy=http://web-proxy.corp.xx.com:8080 /etc/yum.repos.d/rhel-source.repo 里面改成ena ...
-
BZOJ3786星系探索——非旋转treap(平衡树动态维护dfs序)
题目描述 物理学家小C的研究正遇到某个瓶颈. 他正在研究的是一个星系,这个星系中有n个星球,其中有一个主星球(方便起见我们默认其为1号星球),其余的所有星球均有且仅有一个依赖星球.主星球没有依赖星球. ...