杭电 1005

Number Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 157162 Accepted Submission(s): 38477

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

此题不肯能将每一种情况都记录下来，考虑mod7之后，有0,1,2,3,4,5,6 7种情况，则对每一种a,b, f(n)必然构成了一个循环队列

由于f(n)是f(n-1)和f(n-2)的线性组合，故f(n)最多可能有7*7 = 49种情况,若让f(n)一直不出现重复，那么这个循环队列的最大长度必然是49,超过这个长度这个队列就一定会出现重复，这有点类似于鸽巢原理。

所以对于给定的a,b, 我们可以利用一个长度稍大于49的数组记录结果。

然后去寻找队列的最长不重复的子序列，只要发现序列中某个相邻两项和后面某个相邻两项完全相同，则确定出现重复。

代码如下

 1 #include <cstdio>
 2 #include <cstdlib>
 3 int res[55];
 4 
 5 int main(int argc, char const *argv[])
 6 {
 7     int a, b, n;
 8     while(scanf("%d %d %d",&a,&b,&n),a|b|n) {
 9         res[1] = 1;
10         res[2] = 1;
11         int flag = 0;    
12         int from,to;
13         for(int i = 3; i <= n && !flag; i++) {
14             res[i] = (a * res[i-1] + b *res[i-2])%7;
15             for(int j = 2; j <= i-1; j++) {
16                 if(res[i] == res[j] && res[i-1] && res[j-1]) {
17                     flag = 1;
18                     from = j;
19                     to = i;
20                     break;
21                 }
22             }
23         }
24         int ans;
25         if(flag) {
26             ans = res[from+(n-to)%(to-from)];
27         }
28         else {
29             ans = res[n];
30         }
31         printf("%d
",ans);
32     }
33     return 0;
34 }

注：第8行，逗号把最后一个表达式的值当作返回值

比如

int i;
while( scanf("%d",&i) , i != 0 )
{
}
这里的，是一个序点
含义是必须先完成前面的求值（scanf("%d",&i) 的求值，但这里其实我们要的是给i赋值的副效应，scanf("%d",&i)这个表达式的值是没有用的 ），然后再进行右面的求值
所以，逗号表达式尽管只用到最后一个值，但很可能最后一个值依赖于前面求值引起的副效应
这就是为什么要写前面子表达式的原因，也是逗号表达式的真正意义



作者：薛非
链接：https://www.zhihu.com/question/22710102/answer/22455046
来源：知乎
著作权归作者所有，转载请联系作者获得授权。