这道题初看可以直接递归解决,但是 n 的取值过大时会发生栈溢出,无法解决这一问题。仔细思考之后发现,输入A、B、n之后,A、B的值就确定了,f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7
的值只取决于 f(n - 1) 和 f(n - 2) 的值。
假如我们知道了A、B的值,那么 f(3) 的值就可以由递推式得出,f(4) 的值也可由 f(2) 和 f(3) 得出,就像多米诺骨牌一样,后面的所有都可以确定了。由此可知,我们知道前面 f(n - 1) 和 f(n - 2) 的值,就可以得出 f(n) 的值了。
f(n - 1) 和 f(n - 2) 的取值范围均为 0~6 共 7 种情况,两个的组合共 7×7=49 种情况, 也就是 50 次以后,一定会有重复的情况。比如 50 次里出现[0][0]
两次,我们就可以断定 f(n) 的值是循环出现的,因为前面两个数一定可以确定第三个数,后面的数也都随之确定,所以再次出现相同的两个数时,下一个数也一定和上一次相等。(例如 f(3)=3,f(4)=4,而确定的 f(5)=5,当 f(35)=3,f(36)=4 的时候,f(37)一定等于5,循环的周期就是 35-3=32)。但是值得注意的是,循环的周期不一定是 49,可能不到 49 就开始循环了,因此我们还是需要找到循环周期是多少。
还有一点,f(1) 和 f(2) 是人为给出的,可能不在循环之内,因此我选择从 f(3) 开始算循环周期。
所以代码如下:
#include<stdio.h>
int main(){
long a,b,n;
while(scanf("%ld%ld%ld",&a,&b,&n) != EOF){
if(a==0 && b==0 && n==0) return 0;
int f[53];
f[1]=1,f[2]=1;
int t; //循环周期
for(int i=3;i<53;i++){ //计算f[1]~f[52]的值
f[i] = (a*f[i-1] + b*f[i-2]) % 7;
}
for(int j=5;j<53;j++){ //找循环周期t
if(f[j]==f[3] && f[j+1]==f[4]){
t = j-3; //从第三个开始找,要减3得到周期
break;
}
}
int ans = f[(n-3)%t+3]; //先减3算出在循环周期里的次序,再加3得到对应数组下标次序
printf("%d\n",ans);
}
return 0;
}
网友评论