posts - 99,  comments - 8,  trackbacks - 0
hdu 1005
//本来以为是一道简单题谁知道。。。。
//用递归写想都不要想，绝对超时，所以还应当回到题目本身的分析上来
//正确思路是：因为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 雪黛依梦 阅读(1466) 评论(1)  编辑 收藏 引用 所属分类: 简单题 、技巧题

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

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


Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2011年7月>
日一二三四五六
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜