http://acm.hdu.edu.cn/showproblem.php?pid=1005A 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).
1 <= A, B <= 1000, 1 <= n <= 100,000,000
解:
f(n) = (A * f(n - 1) + B * f(n - 2)) %7
= (A * f(n - 1) %7 + B * f(n - 2) %7) %7
所以對(duì)于給定的A和B,可以先打表,找出數(shù)列的循環(huán)部分. 鴿巢原理知,狀態(tài)總數(shù)不會(huì)超過7*7
注意循環(huán)節(jié)不一定從f(3)開始...
1
#include <iostream>
2using namespace std;
3
4int a,b,n,x,y,l,h,m[7][7],q[300];
5
int main()
{
6
while(scanf("%d%d%d",&a,&b,&n)!=EOF && (a||b||n)){
7
memset(m, 0, sizeof(m));
8 q[1] = q[2] = 1;
9 x = y = 1; l=3;
10 while(m[x][y]==0){ //該狀態(tài)還未經(jīng)歷過,則擴(kuò)展
11 q[l] = (a*x+b*y)%7;
12 m[x][y] = l;
13 y = x;
14 x = q[l++];
15
}
16 //此時(shí),q[1h-1]為前面的非循環(huán)部分
17 //q[hl-1]為循環(huán)節(jié)
18 h = m[x][y]; //循環(huán)節(jié)的起始位置
19 if(n<h) printf("%d\n",q[n]);
20 else printf("%d\n",q[((n-h)%(l-h))+h]);
21 }
22 return 0;
23
}
posted on 2009-04-25 11:55
wolf5x 閱讀(909)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm_icpc