noip历届复赛试题及解析
计算系数
【问题描述】
给定一个多项式(ax + by)^k,请求出多项式展开后(x^n)*(y^m)项的系数。
【输入】
输入文件名为 factor.in。
共一行,包含 5 个整数,分别为a,b,k,n,m,每两个整数之间用一个空格隔开。
【输出】
输出文件名为 factor.out。
输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对10007 取模后的结果。
【输入输出样例】

【数据范围】
对于 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。
【考察知识点】
数论/二项式系数/组合
【思路】学OI的应该知道二项式系数/组合数/杨辉三角,再不行手推几个也就能知道ans=C(k,n)*(a^n)*(b^m)
这里由于是取模,同余只能用于加和乘。但又要算组合数,而组合数公式里有除法,我因此纠结了很久很久,甚至最后都有写高精加减乘除模的想法。
瞬间灵光一闪,C(k,n)=C(k-1,n)+C(k-1,n-1),行了!注意要边加边mod,否则跟没想到一样。
【时间复杂度】
O(k^2)
program factor;
//uses sysutils;
const
proname='factor';
yu=10007;
var
fin,fout:text;
i,j,k,m,n,l,r,s,t,x,y:longint;
a,b:int64;
ans:int64;
NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告day1NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺...
NOIP2011提高组解题报告day1_调查/报告_表格/模板_应用文书。noip历届复赛试题及解析铺地毯 【问题描述】 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形...
NOIP2011提高组复赛DAY1解题报告_初一数学_数学_初中教育_教育专区。NOIP2011提高组复赛DAY1解题报告NOIP2011DAY1 解题报告 By 北京一零一中学 张子威(c++) 首先,...
NOIP2011 提高组 解题报告_军事/政治_人文社科_专业资料。NOIP 2011 November 13, 2011 Contents 1 Day I 1.1 carpet . . . . . . . . . . . . ...
Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛 ...
关键词:noip2011提高组day2 1/2 相关文档推荐 NOIP2011 提高组 试题 Day... 4页 2财富值 NOIP2011提高组解题报告da... 9页 5财富值 NOIp2011提高组复赛...
冲刺NOIP2011长乐一中day2解题报告 隐藏>> 解题报告题 1、内存管理题目大意:对于每次申请,使用最小的内存块,对于每次访问,给出是否允许。 朴素算法:每次扫描一遍,...
全国信息学奥林匹克联赛(NOIP2011)复赛 提高组 day2 全国信息学奥林匹克联赛(NOIP... NOIP2011 提高组 Day2 4页 免费 NOIP2011提高组解题报告... 9页 2下载券...
noip 2012 提高组 解题报告_学科竞赛_高中教育_教育专区。noip 2012 提高组 ... NOIP 2012 提高组 解题报... 4页 免费 NOIP2012提高组day1 7页 免费 ...
noip2010提高组解题报告_IT/计算机_专业资料。noip2010提高组解题报告NOIP2010 解题报告(提高) 作者: 作者:张宇昊所有见解仅供参考 考试时。。。发挥 已经不错了...
热门文档