HDU/1005

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Number Sequence	★☆☆☆☆	答案正确	100	2015-02-06 11:36:22	遗漏情况（0）

• 来自寒假练习：Only a signing tool ! F题
• 原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1005

题意

已知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; } } } }