2012福建省信息学奥林匹克CCF-NOIP夏令营第七天训练(附解题思路及参考程序).doc

(完整版)2012福建省信息学奥林匹克CCF NOIP夏令营第七天训练(附解题思路及参考程序)2012福建省信息学奥林匹克CCF NOIP夏令营第七天训练(附解题思路及参考程序）问题名称文件名输入文件输出文件时限分值Couple numbercouplecouple.incouple。out1s100广义斐波那契数列sequencesequence 。insequence 。out1s100车的放置placeplace。inplace。out1s100内存限制均为256MCouple number（couple）【问题描述】任何一个整数N都能表示成另外两个整数a和b的平方差吗？如果能,那么这个数N就叫做Couple number.你的工作就是判断一个数N是不是Couple number。【输入文件】仅一行，两个长整型范围内的整数n1和n2，之间用1个空格隔开。【输入文件】输出在n1到n2范围内有多少个Couple number.注意：包括n1和n2两个数，且n1n2，n2 - n1 (a+b)（a-b)=n如果n是奇数,则a，b一奇一偶，而n=1n,所以，令a=（n+1）/2，b=（n-1)/2,即n一定是Couple number.如果n是偶数，则a,b同奇同偶，此时如果n mod 4=2，则n一定是拆成一奇一偶的和,即x+y和x-y的值一定是一奇一偶，这种情况下x,y肯定无整数解，所以此时的n一定不是Couple number;如果n mod 4=0,则a=n/4+1,b=n/4-1，即n一定是Couple number。参考程序:var x，y,i，ans：longint；begin assign（input,couple。in）; reset(input)； readln(x,y); close(input）; ans：=0； for i：=x to y do begin if odd(i) then inc(ans） else if i mod 4=0 then inc（ans); end; assign(output,couple.out）; rewrite（output）; writeln(ans)； close(output）;end。广义斐波那契数列由于n巨大，从头开始一一推算数列的每一项是不可能的。又由于m巨大，利用数列对m取余的余数循环性质也是不可能的。而本题采用的算法是由原本的递推公式（数列中某项与前两项的关系）,推导得出数列中某项和与其遥遥相隔的连续两项之间的关系（比如a100与a1,a2之间的关系）。推导过程如下。an=p*an1+qan2an=（pp+q）*an-2+(pq）an3an=(（p*p+q)p+pq）*an-3+（p*p+q)*q）an4an=ck*ank+dk*ank1（其中c、d数列的递推公式是cn=p*cn-1+dn1，dn=qcn1,c1=p，d1=q）如此，我们由最初两项向后推算时每步的步长可以非常大,忽略中间的许多项,从而节省时间.首先根据给定的p、q以及上述递推公式计算出c29999和d29999除以m的余数。然后根据a1和a2,计算出第三项。根据前三项以及开始时求出的c，d数列中那两项的余数，计算出a30001和a30002除以m的余数。根据这两项的余数，又可计算出a30003除以m的余数。这样就由起初的连续三项一下子推出30000项后的连续三项。当n巨大时，用这样的方法不断向前推接近n，到与n的距离不足30000时再一项项推算过去，直到求出an出除以m的余数为止.可以在给定的时间内完成。参考程序：var i，j，k，n,m,p,q:longint; a，b,c，d:qword; f:array1.。30000of qword;procedure setup； begin assign（input，sequence。in)； reset(input）; assign(output,sequence。out); rewrite（output）； end；procedure endit； begin close（input）； close（output）; end;begin setup； readln（p，q,f1,f2，n，m）； p：=p mod m; q:=q mod m； f1:=f1 mod m； f2:=f2 mod m； f3：=(p*f2+qf1) mod m; a:=p; b:=q； for i：=2 to 29999 do begin c：=(p*a+b) mod m； d:=（q*a) mod m； a：=c； b：=d; end； while (n30000） do begin dec（n,30000）; f1：=(a*f2+bf1） mod m; f2:=(af3+b*f2） mod m； f3：=(pf2+qf1) mod m; end; for i：=4 to n do fi：=(p*fi1+q*fi-2） mod m； writeln（fn); endit;end。车的放置在一个NM的棋盘中，放K个相互不攻击的车的方案数N行中选K行放车，方案数C(N， K）变成一个KM的棋盘，接下来这K行中，每一行放一个车,车的列不能相同，即列构成了M取K的排列，方案数P(N， K)总方案数C(N， K）P(N, K)考虑原棋盘先在上部（ab）放i个车，剩下K i个车放在下部（(a+c)d）在ab放i个车方案数C（a, i)P(b, i）下部有i列不能放车，则等价于一个（a + c i）d的一个棋盘放K i个车方案数C（a + c i， K i）P（d， K i）总C(a， i)P(b， i)C（(a + c i， K i）P(d, K i)枚举i，求和即为答案参考程序：#include#includecstdioinclude#includecstringincludevector#includemapincludecmath#includeusing namespace std;const int MXN = 2002;int a, b， c， d， k;long long CMXNMXN;long long PMXNMXN；long long ans；long long calc(int n， int m， int k） /if (k n | k m） return 0; return Cnk * Pmk % 100003;int main（) freopen(”place。in, r”， stdin); freopen（”place.out, ”w， stdout); memset（C， 0， sizeof（C)； memset（P, 0, sizeof（P); for（int i = 0； i MXN； i+) for（int j = 0； j = i； j+) if(j = 0 j = i） Cij = 1； else Cij = （Ci 1j + Ci - 1j 1) 100003； for（int i = 0; i a b c d k; ans = 0; for （int i = 0； i = min(min(a, b)， k); i+) ans += calc(a, b, i） * calc(a + c - i， d, k i) 100003； ans %= 100003; cout ans endl;