【NOIP2011】计算系数
Description
给定一个多项式 (ax+by)^k ,请求出多项式展开后 x^n * y^m 项的系数。
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
数学,递推
解析
全班数学垫底的我竟然在讲数学题!!!
好吧它确实是一道数学题。
首先,二项式定理了解一下:
对于a与b的和的n次幂,
有:
因此,原式可化简为:
(ax)n (by)m × C(k,n) //实在没图片了
所以只要求组合数取模,快速幂就行了。
然后,我就想到了拓展欧几里得,逆元,卢卡斯定理等神奇的东西。。。
其实并不需要这么复杂,
聪明的中国人早就有自己的东西:杨辉三角!!
所以只要递推求组合数就可以了!!
最后上AC代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std; const int Mod=;
int a,b,k,m,n;
int f[][]; ll power(int a,int b){
ll r=;
while(b){
if((b&)) r=r*a%Mod;
a=(ll)a*a%Mod;
b>>=;
}
return r;
} int main(){
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
for(int i=;i<=k;i++){
f[i][]=;
}
for(int i=;i<=k;i++){
for(int j=;j<=i;j++){
f[i][j]=((ll)f[i-][j]+(ll)f[i-][j-])%Mod;
}
}
ll ans=(ll)f[k][n]%Mod*(ll)power(a,n)%Mod*(ll)power(b,m)%Mod;
ans%=Mod;
printf("%lld\n",ans);
return ;
}
题解 【NOIP2011】计算系数的更多相关文章
-
NOIP2011 计算系数
1计算系数 给定一个多项式 (ax + by)k ,请求出多项式展开后 x n y m 项的系数. [输入] 输入文件名为 factor.in. 共一行,包含 5 个整数,分别为 a,b,k,n,m, ...
-
luoguP1313 [NOIp2011]计算系数 [组合数学]
题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数. 输入输出格式 输入格式: 输入文件名为factor.in. 共一行,包含5 个整数,分别为 a ,b ,k , ...
-
[NOIP2011] 计算系数(二项式定理)
题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数. 输入输出格式 输入格式: 输入文件名为factor.in. 共一行,包含5 个整数,分别为 a ,b ,k , ...
-
[noip2011]计算系数+二项式定理证明
大水题,二项式定理即可(忘得差不多了) 对于一个二项式,\((a+b)^n\)的结果为 \(\sum_{k=0}^{k<=n}C_{n}^{k}a^{n-k}b^k\) 证明: 由数学归纳法,当 ...
-
NOIP2011计算系数;
#include<cmath> #include<algorithm> #include<stdio.h> #include<iostream> #de ...
-
NOIP 2011 计算系数
洛谷 P1313 计算系数 洛谷传送门 JDOJ 1747: [NOIP2011]计算系数 D2 T1 JDOJ传送门 Description 给定一个多项式(ax + by)k,请求出多项式展开后x ...
-
luoguP1313 计算系数 题解(NOIP2011)
P1313 计算系数 题目 #include<iostream> #include<cstdlib> #include<cstdio> #include<cm ...
-
洛谷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 ...
随机推荐
-
svn工具安装下载Tomcat源码以及导入eclipse
安装 1.svn下载地址 https://tortoisesvn.net/downloads.html 2.语言包下载 3.先安装svn,在直接安装语言包 4.桌面右键可以看到相关svn信息 下载To ...
-
node(websocket)
websocket原本是html5下实现长链接的一个特性,当前已被众多浏览器支持. 在websocket协议中,首先通过http交换一次握手,明确将协议升级至websocket.同时建立一个TCP通道 ...
-
.net开发笔记(十三) Winform常用开发模式第一篇
上一篇博客最后我提到“异步编程模型”(APM),之后本来打算整理一下这方面的材料然后总结一下写篇文章与诸位分享,后来在整理的过程中不断的延伸不断地扩展,发现完全偏离了“异步编程”这个概念,前前后后所有 ...
-
Java常用命令
jps 查看java进程的PID java -XX:+PrintFlagsInitial 显示所有可设置参数及默认值 java -XX:+PrintFlagsFinal 获取到所有可 ...
-
JDK Tools - xjc: 将 XML Schema 编译成 Java 类
xjc 是 JAXB 将 xsd 生成 Java 类的工具. 命令格式 xjc [ options ] schema file/URL/dir/jar ... [-b bindinfo ] ... 命 ...
-
使用viewpager实现广告条轮询的效果
先上效果图: viewpager是google在v4-support包中提供的,使用时与listview类似,度需要提供一个adapter, 只不过viewpager提供的是PagerAdapter ...
-
VC编程之设置客户区背景图片
在很多系统中出于美观的需要常常要设置背景图片.下面我介绍一种在客户区设置背景图片的简单方法. 1 .将背景bmp 图片导入到工程,资源ID 这里假设为 IDB_BITMAP1 2 .在视图类添加如下代 ...
-
关于PHP魔术方法__call的一点小发现
好久没有上博客园写文章了,今晚终于有点空了,就来写一下昨天的一点小发现. 我自己所知,C++,Java的面向对象都有多态的特点,而PHP没有,但PHP可以通过继承链方法的重写来实现多态的属性.而魔术方 ...
-
spring framework体系结构及内部各模块jar之间的maven依赖关系
很多人都在用spring开发java项目,但是配置maven依赖的时候并不能明确要配置哪些spring的jar,经常是胡乱添加一堆,编译或运行报错就继续配置jar依赖,导致spring依赖混乱,甚至下 ...
-
解决使用maven的java web项目导入后出现的有关问题 -cannot be read or is not a valid ZIP file
解决使用maven的java web项目导入后出现的有关问题 -cannot be read or is not a valid ZIP file 错误问题:虽然查找repository目录下是有 ...