摘要
题目链接 |
难度等级 |
完成状态 |
完成分数 |
最后编辑时间 |
失误原因(初次提交分数)
|
Number Sequence
|
★☆☆☆☆
|
答案正确
|
100
|
2015-02-06 11:36:22
|
遗漏情况(0)
|
题意
已知f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7,求f(n)。
题解
- O(n)肯定会T,在Excel打了个表,发现基本都有循环节的,于是就去找循环节。
- 只要找到连续两位是出现过,就说明出现循环节了,这个可以另外开一个数组记录一下。
- 找到循环节减一减模一模就很容易算出答案了,根据……嗯哼……抽屉原理,最多出现7*7种也要出现重复了么,所以实际复杂度是很小的。
代码
1005.cpp代码已折叠
展开折叠内容
|
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- using namespace std;
- #define ci const int &
-
- const int nv2(ci _x,ci _y)
- {
- return _x*9+_y;
- }
- int a[1000000]={},last[700],A,B,C,repeatBegin,repeatEnd,repeatLen;
- int main()
- {
- while(1)
- {
- memset(last,0,sizeof(last));
- a[1]=a[2]=1;
- cin>>A>>B>>C;
- if(!A&&!B&&!C)//fixed遗漏结尾判断//
- return 0;
- if(C<=2)//fixed增加C<=2特判//
- {
- cout<<1<<endl;
- continue;
- }
- last[nv2(1,1)]=2;
- for(int i=3;i<=C;++i)
- {
- a[i]=(A*a[i-1]+B*a[i-2])%7;
- if(last[nv2(a[i],a[i-1])])
- {
- repeatBegin=last[nv2(a[i],a[i-1])]+1;
- repeatEnd=i;
- repeatLen=repeatEnd-repeatBegin+1;
- cout<<a[(C-repeatBegin+1)%repeatLen+repeatBegin-1]<<endl;
- break;
- }
- last[nv2(a[i],a[i-1])]=i;
- if(i==C)
- {
- cout<<a[C]<<endl;
- break;
- }
- }
- }
- }
|