bzoj 5313: 新Fib数列 — 暴力
Contents
5313: 新Fib数列
Time Limit: 2 Sec Memory Limit: 16 MB
Description
天地合，乃敢不君绝？我们发现求出斐波那契数列在某种意义下可以作为解决一些有意义问题的方法，特别是在模
5意义下的某种组合，或许可以破解敌方的密码系统。出题人太懒了，对于算斐波那契数列这种难事，丌能找到简
便方法，因此他就懒得丌想做了（即使想做可能要买上一条1PB的内存条）。他找到了善于思考、 用计算机快速解
决问题的你！你能帮帮他吗？
斐波那契数列的定义为 F(n)=F(n-1)+F(n-2)。
Input
现有Q个询问， 每个询问都给出一个Qi。
对于每个询问
请你求出并输出斐波那契数列在模 5 意义下的第Qi项，每个询问的输出占一行。
Q<=10^6 Qi<=2*10^9
请留意本题数据范围。 本题共有25个测试点。
Output
如题
Sample Input
9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
Sample Output
1
1
2
3
0
3
3
1
4
1
2
3
0
3
3
1
4
HINT
好久不写blogs了，水一发题。。
我们发现只要连续两位都和之前相同答案就循环了，所以由数学证明循环节<=5*5，最后我们发现循环节是20
证明的话，就是两个相邻的数只有5*5种本质不同的组合，所以25个数内就会有重复的
好水啊qaq
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 100010
char xB[1<<15],*xS=xB,*xTT=xB;
#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
#define isd(c) (c>='0'&&c<='9')
inline int rd(){
char xchh;
int xaa;
while(xchh=getc(),!isd(xchh));(xaa=xchh-'0');
while(xchh=getc(),isd(xchh))xaa=xaa*10+xchh-'0';return xaa;
}
int Q,x;
int f[22];
int main()
{
f[0]=1;f[1]=1;
for(int i=2;;i++)
{
f[i]=(f[i-1]+f[i-2])%5;
if(f[i]==f[1]&&f[i-1]==f[0]) break;
}
Q=rd();
while(Q--)
{
x=rd()-1;x%=20;
printf("%d\n",f[x]);
}
return 0;
}
发表评论