注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[hdu]1005 Number Sequence  

2012-07-30 10:42:03|  分类: HDU |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Number Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 61183    Accepted Submission(s): 13951


Problem Description
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).
 

Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
 

Output
For each test case, print the value of f(n) on a single line.
 

Sample Input
1 1 3 
1 2 10 
0 0 0
 

Sample Output
5
 

Author
CHEN, Shunbao
 

Source
 

Recommend
JGShining
 
题目意思很简单,就不描述了。这题可以找规律来做。就是找循环周期。
代码如下:


#include<iostream>
using namespace std;
int main()
{
int A,B,n,f[100];
while(~scanf("%d%d%d",&A,&B,&n))
{
if(A == 0 && B == 0 && n == 0) break;
int i,j;
f[1] = 1,f[2] = 1;
int loop = 0,beg = 0;
for(i = 3;i < 100;i ++)
{
f[i]= (A * f[i - 1] + B * f[i - 2]) % 7;
for(j = 2;j <= i;j ++)
{
if(f[i] == f[j] && f[i - 1] == f[j - 1])
{
loop = i - j;
beg = j;
//从j开始循环,循环周期为i - j,循环开始位置为j;
break;
}
}
}
if(n < beg) cout<<f[n]<<endl;
else cout<<f[beg + (n - beg) % loop]<<endl;
}
return 0;
}


由于是对7除余,所以循环是在49内,我们可以直接在49内找
代码:


#include<iostream>
using namespace std;
int main()
{
int A,B,n,f[100];
while(~scanf("%d%d%d",&A,&B,&n))
{
if(A == 0 && B == 0 && n == 0) break;
int i,j;
f[1] = 1,f[2] = 1;
A %= 7,B %= 7;
for(int i = 3;i < 50;i ++)
{
f[i]= (A * f[i - 1] + B * f[i - 2]) % 7;
}
cout<<f[n % 49]<<endl;
}
return 0;
}



看到其他牛说可以用矩阵乘法做,于是=。 =终于不得不面对矩阵...
不知道什么是矩阵的孩子直接百度吧...
我们可以把f[n]= (A * f[n - 1] + B * f[n - 2])转化成
[a b1 0] ×[f(n-1)f(n-2)]=[f(n)f(n-1)]
再对一项也就是:


[a b1 0]×[a b1 0]×[f(n-2)f(n-3)]=[f(n)f(n-1)]


这样的一个矩阵,一直迭代下去也就成了 :
[a b1 0]n-2×[11]=[f(n)f(n-1)






]


也就是需要一个矩阵{a,b,1,0}
第一次接触矩阵,代码是模仿某牛来的:


#include<iostream>
using namespace std;
int matrix[2][2],temp[2][2];
int A,B,n;

void power(int n)
{
if(n == 1)
{
matrix[0][0] = A % 7;
matrix[0][1] = B % 7;
matrix[1][0] = 1;
matrix[1][1] = 0;
}
else if(n == 2)
{
matrix[0][0] = (A * A + B) % 7;
matrix[0][1] = (A * B) % 7;
matrix[1][0] = A % 7;
matrix[1][1] = B % 7;
}
else
{
power(n / 2);
temp[0][0] = (matrix[0][0] * matrix[0][0] + matrix[0][1] * matrix[1][0]) % 7;
temp[0][1] = (matrix[0][0] * matrix[0][1] + matrix[0][1] * matrix[1][1]) % 7;
temp[1][0] = (matrix[1][0] * matrix[0][0] + matrix[1][1] * matrix[1][0]) % 7;
temp[1][1] = (matrix[1][0] * matrix[0][1] + matrix[1][1] * matrix[1][1]) % 7;
if(n & 1)
{
matrix[0][0] = (temp[0][0] * A + temp[0][1]) % 7;
matrix[0][1] = (temp[0][0] * B) % 7;
matrix[1][0] = (temp[1][0] * A + temp[1][1]) % 7;
matrix[1][1] = (temp[1][0] * B) % 7;
}
else
{
matrix[0][0] = temp[0][0] % 7;
matrix[0][1] = temp[0][1] % 7;
matrix[1][0] = temp[1][0] % 7;
matrix[1][1] = temp[1][1] % 7;
}
}
}


int main()
{
int f[2] = {1, 1};
while (~scanf ("%d%d%d", &A, &B, &n))
{
if (A == 0 && B == 0 && n == 0) break ;
if (n == 1 || n == 2)
{
printf ("1\n") ;
continue ;
}
else
{
power(n - 2);
cout << (matrix[0][0] + matrix[0][1]) % 7 << endl;
}
}
return 0;
}




  评论这张
 
阅读(102)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018