Number Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 154006    Accepted Submission(s): 37586 Problem Description A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n).   Input The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.   Output For each test case, print the value of f(n) on a single line.   Sample Input 1 1 3 1 2 10 0 0 0   Sample Output 2 5   Author CHEN, Shunbao  

Source

第一种方法：找出循环节s，

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int f[100000001]; int main() { f[1]=1; f[2]=1; int i,n,j; int a,b; while(scanf("%d%d%d",&a,&b,&n)!=EOF&&(a||b||n)) { int s=0; for(i=3; i<=n; i++) { f[i]=(a*f[i-1]+b*f[i-2])%7; for(j=2; j<i; j++) if(f[i-1]==f[j-1]&&f[i]==f[j]) { s=i-j; break; } if(s>0)break; } if(s>0) { f[n]=f[(n-j)%s+j]; } cout<<f[n]<<endl;; } return 0; } 第二种，由于最大mod为7，由鸽巢原理知最大状态数不超过7^7

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <set> using namespace std; int main() { int f[1001],n; int a,b,i; while(scanf("%d%d%d",&a,&b,&n)&&a+b+n) { f[1]=1; f[2]=1; for(i=3;i<=49;i++) { f[i]=(a*f[i-1]+b*f[i-2])%7; } printf("%d\n",f[n%48]); } return 0; }