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

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

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

问题名称
文件名
输入文件
输出文件
时限
分值
Couple number
couple
couple.in
couple。out
1s
100
广义斐波那契数列
sequence
sequence 。in
sequence 。out
1s
100
车的放置
place
place。in
place。out
1s
100
内存限制均为256M

Couple number（couple）

【问题描述】
任何一个整数N都能表示成另外两个整数a和b的平方差吗？如果能,那么这个数N就叫做Couple number.你的工作就是判断一个数N是不是Couple number。

【输入文件】
仅一行，两个长整型范围内的整数n1和n2，之间用1个空格隔开。

【输入文件】
输出在n1到n2范围内有多少个Couple number.
注意：包括n1和n2两个数，且n1〈n2，n2 - n1 <= 10 000 000。

【输入样例】
1 10

【输出样例】
7
广义斐波那契数列(sequence)

【问题描述】
广义的斐波那契数列是指形如an=p*an—1+q＊an-2的数列。今给定数列的两系数p和q,以及数列的最前两项a1和a2,另给出两个整数n和m，试求数列的第n项an除以m的余数。

【输入文件】
输入包含一行6个整数。依次是p，q，a1,a2,n，m,其中在p，q,a1，a2整数范围内，n和m在长整数范围内。

【输出文件】
输出包含一行一个整数，即an除以m的余数。

【输入样例】
1 1 1 1 10 7

【输出样例】
6

【样例说明】
数列第10项是55，除以7的余数为6。
车的放置(place）

【问题描述】
有下面这样的一个网格棋盘，a，b,c，d表示了对应边长度，也就是对应格子数.
a
b
c
d

当a=b=c=d=2时，对应下面这样一个棋盘

要在这个棋盘上放K个相互不攻击的车，也就是这K个车没有两个车在同一行，也没有两个车在同一列,问有多少种方案。同样只需要输出答案mod 100003后的结果。

【输入文件】
输入文件place.in的第1行为有5个非负整数a， b， c， d和k。

【输出文件】
输出文件place。out包括1个正整数,为答案mod 100003后的结果。

【样例输入】
2 2 2 2 2

【样例输出】
38

【数据规模与约定】
对于部分数据，有b = 0；
对于部分数据,有a，b，c,d≤4。
对于100％的数据，a，b,c，d,k≤1000，且保证了至少有一种可行方案。
Couple number
a＊a-b*b=n 〈=> (a+b)（a-b)=n
如果n是奇数,则a，b一奇一偶，而n=1＊n,所以，令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*an—1+q＊an—2
an=（p＊p+q）*an-2+(p＊q）＊an—3
an=(（p*p+q)＊p+p＊q）*an-3+（（p*p+q)*q）＊an—4
……
an=ck*an—k+dk*an—k—1
（其中c、d数列的递推公式是cn=p*cn-1+dn—1，dn=q＊cn—1,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:array[1.。30000］of 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,f［1］,f[2]，n，m）；
p：=p mod m;
q:=q mod m；
f[1］:=f［1］ mod m；
f[2]:=f［2］ mod m；
f[3］：=(p*f［2］+q＊f[1］) 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 (n〉30000） do
begin
dec（n,30000）;
f［1］：=(a*f[2］+b＊f［1］） mod m;
f［2］:=(a＊f［3］+b*f[2]） mod m；
f[3]：=(p＊f[2］+q＊f[1]) mod m;
end;
for i：=4 to n do
f[i]：=(p*f［i—1］+q*f[i-2]） mod m；
writeln（f［n]);
endit;
end。
车的放置
在一个N×M的棋盘中，放K个相互不攻击的车的方案数
N行中选K行放车，方案数C(N， K）
变成一个K×M的棋盘，接下来这K行中，每一行放一个车,车的列不能相同，即列构成了M取K的排列，方案数P(N， K)
总方案数C(N， K）×P(N, K)
考虑原棋盘
先在上部（a×b）放i个车，剩下K – i个车放在下部（(a+c)×d）
在a×b放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<iostream>
#include<cstdio〉
＃include<string>
#include〈cstring>
＃include〈vector〉
#include〈map〉
＃include〈cmath>
#include<algorithm>
using namespace std;
const int MXN = 2002;
int a, b， c， d， k;
long long C［MXN］[MXN];
long long P［MXN］［MXN］；
long long ans；
long long calc(int n， int m， int k） ｛
//if (k 〉 n || k > m） return 0;
return C［n][k] * P［m］［k］ % 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） ｛
C［i］［j] = 1；
｝ else {
C[i］［j] = （C［i — 1］[j] + C[i - 1]［j — 1]) ％ 100003；
｝
}

for（int i = 0; i < MXN; i++) ｛
P［i］［0] = 1;
for(int j = 1； j 〈= i； j++）
P［i］[j］ = P[i］[j — 1] ＊ (i — j + 1） % 100003；
}
cin >> 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;
}