posts - 99,  comments - 8,  trackbacks - 0
//本来以为是一道简单题谁知道。。。。
//用递归写想都不要想,绝对超时,所以还应当回到题目本身的分析上来
//正确思路是:因为mod7的关系,而且f(1)=f(2)=1,所以f(n)的值是循环分布的,而且一定会回到f(n-1)=f(n)=1,
//并且还可得出,这个循环不大于49,因为相邻连个f只有7种取值,这样f(n-1)和f(n)共有49种组合。
//所以,只要找出循环因子即可,寻找方法正是根据f(n-1)=f(n)再次出现的地方来计算
//可以首先为这个题目写一个测试的程序设定一个 a   b   n(n 比较小时)  的值   看看输出规律
 1#include <stdio.h>
 2#include <stdlib.h>
 3int f[51];
 4int main ()
 5{
 6    int a, b, n; 
 7    while ( scanf ("%d %d %d"&a , &b, &n) != EOF && a != 0 && b != 0 && n != 0 )
 8    {
 9          f[1= f[2= 1;
10          int i;
11          for (i = 3; i < 51; i ++)
12          {
13              f[i] = (a * f[i - 1+ b * f[i - 2]) % 7;
14              if ( f[i] == 1 &&  f[i - 1== 1 )   //找到循环因子 i  
15              {
16                   break;
17              }

18          }

19          
20          n = n % (i - 2);
21          if (n == 0)   //刚好经过一个循环 
22          printf ("%d\n", f[i - 2]);   //开始时,我是因为看了测试程序,把这里设定为输出 0 这种想法是错的,太片面了,因为数据范围很大  
23          else         
24          printf ("%d\n", f[n]);
25    }

26    //system ("pause");
27    return 0;
28}
 
29
30
posted on 2010-08-24 14:01 雪黛依梦 阅读(1443) 评论(1)  编辑 收藏 引用 所属分类: 简单题技巧题

FeedBack:
# re: hdu 1005
2011-10-20 14:56 | WonderMan
递归想都不要想?矩阵乘法+快速幂不高兴  回复  更多评论
  

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


<2011年10月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜