posts - 43,  comments - 9,  trackbacks - 0
http://acm.hdu.edu.cn/showproblem.php?pid=1005
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).
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
所以对于给定的A和B,可以先打表,找出数列的循环部分. 鸽巢原理知,状态总数不会超过7*7
注意循环节不一定从f(3)开始...

 1#include <iostream>
 2using namespace std;
 3
 4int a,b,n,x,y,l,h,m[7][7],q[300];
 5int main(){
 6    while(scanf("%d%d%d",&a,&b,&n)!=EOF && (a||b||n)){
 7        memset(m, 0sizeof(m));
 8        q[1= q[2= 1;
 9        x = y = 1; l=3;
10        while(m[x][y]==0)//该状态还未经历过,则扩展
11            q[l] = (a*x+b*y)%7;
12            m[x][y] = l;
13            y = x;
14            x = q[l++];
15        }

16        //此时,q[1h-1]为前面的非循环部分
17         //q[hl-1]为循环节
18        h = m[x][y]; //循环节的起始位置
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 阅读(900) 评论(0)  编辑 收藏 引用 所属分类: acm_icpc

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2009年9月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜