摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
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代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. using namespace std;
  5. #define ci const int &
  6.  
  7. const int nv2(ci _x,ci _y)
  8. {
  9. return _x*9+_y;
  10. }
  11. int a[1000000]={},last[700],A,B,C,repeatBegin,repeatEnd,repeatLen;
  12. int main()
  13. {
  14. while(1)
  15. {
  16. memset(last,0,sizeof(last));
  17. a[1]=a[2]=1;
  18. cin>>A>>B>>C;
  19. if(!A&&!B&&!C)//fixed遗漏结尾判断//
  20. return 0;
  21. if(C<=2)//fixed增加C<=2特判//
  22. {
  23. cout<<1<<endl;
  24. continue;
  25. }
  26. last[nv2(1,1)]=2;
  27. for(int i=3;i<=C;++i)
  28. {
  29. a[i]=(A*a[i-1]+B*a[i-2])%7;
  30. if(last[nv2(a[i],a[i-1])])
  31. {
  32. repeatBegin=last[nv2(a[i],a[i-1])]+1;
  33. repeatEnd=i;
  34. repeatLen=repeatEnd-repeatBegin+1;
  35. cout<<a[(C-repeatBegin+1)%repeatLen+repeatBegin-1]<<endl;
  36. break;
  37. }
  38. last[nv2(a[i],a[i-1])]=i;
  39. if(i==C)
  40. {
  41. cout<<a[C]<<endl;
  42. break;
  43. }
  44. }
  45. }
  46. }

著作权声明[编辑]

关于[编辑]