首页 > 其他 > 详细

HDU1005 Number Sequence

时间:2014-03-24 06:37:47      阅读:439      评论:0      收藏:0      [点我收藏+]

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1005

 

本来看到题目分类里说这是一道水题,然后就想灌一下水,后来做了一下发现还是有些价值的。。。

第一眼看到数据,n有1Y大,直接递推肯定不行的啦,光开数组也得超啊。剩下就是找规律了,f[n]和f[n+1]的组合只有7*7=49种,所以肯定有周期,而且周期在小于50的时候肯定会出现,重点就是找周期了,可以用vis[7][7]二维数组标记下,当出现过的组合再次出现时,就是周期所在了,剩下的就水了。。。

 

 

bubuko.com,布布扣
 1 #include <stdio.h>
 2 #include <string.h>
 3 int s[55],vis[7][7];
 4 int main ()
 5 {
 6     int a,b,n;s[1] = 1;s[2] = 1;
 7     while (~scanf ("%d%d%d",&a,&b,&n)&&(a+b+n))
 8     {
 9         int i;
10         memset (vis,0,sizeof (vis));
11         vis[1][1] = 1;
12         for (i = 3;i<=50;++i)
13         {
14             s[i] =  (a*s[i-1]+b*s[i-2])%7;
15             if (vis[s[i]][s[i-1]])break;
16             vis[s[i]][s[i-1]] = 1;
17         }
18         if (n<=i){printf ("%d\n",s[n]);continue;}
19         int j;
20         for (j = 1;j<=50;++j)
21             if (s[j]==s[i-1]&&s[j+1]==s[i])break;
22         int t = i-j-1,dex;
23         dex = j-1+((n-j+1)%t?(n-j+1)%t:t);
24         printf ("%d\n",s[dex]);
25     }
26     return 0;
27 }
bubuko.com,布布扣

HDU1005 Number Sequence,布布扣,bubuko.com

HDU1005 Number Sequence

原文:http://www.cnblogs.com/GJKACAC/p/3619801.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!