hdu_1005_Number Sequence_201310222120
2024-09-03 02:47:30
Number Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 86547 Accepted Submission(s): 20560
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).
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
2
5
Author
CHEN, Shunbao
Source
Recommend
又是一道给出了运算公式的数学,凡是没有优化的话,超时超内存等等是避免不了的了。(错了好多次就是因为这,百度了下才明白)这题很显然是一个找规律的题目,也就是该题的求解中是存在循环节的。
对于公式 f[n] = A * f[n-1] + B * f[n-2]; 后者只有7 * 7 = 49 种可能,为什么这么说,因为对于f[n-1] 或者 f[n-2] 的取值只有 0,1,2,3,4,5,6 这7个数,A,B又是固定的,所以就只有49种可能值了。由该关系式得知每一项只与前两项发生关系,所以当连续的两项在前面出现过循环节出现了,注意循环节并不一定会是开始的 1,1 。 又因为一组测试数据中f[n]只有49中可能的答案,最坏的情况是所有的情况都遇到了,那么那也会在50次运算中产生循环节。找到循环节后,就可以轻松解决了。
代码如下:
#include <stdio.h>
#include <string.h> int main()
{
int a,b,n;
while(scanf("%d %d %d",&a,&b,&n),a||b||n)
{
int i,xh=;
int f[];
memset(f,,sizeof(f));
f[]=f[]=;
for(i=;i<;i++)
{
f[i]=(a*f[i-]+b*f[i-])%;
if(f[i]==&&f[i-]==)
break;
}
xh=i-;
n=n%xh;
if(n==)
n=xh;
//for(i=1;i<60;i++)
//printf("%d ",f[i]);
printf("%d\n",f[n]);
}
return ;
}
网上简洁做法:
最新文章
- Java多线程之CountDownLatch学习
- 深入JVM-java虚拟机的基本结构
- [知识点]平衡树之Splay
- Java_Java SE6调用动态编译
- Scala Collection简介
- BS架构与CS架构的区别(最全)
- [terry笔记]RMAN综合学习之配置
- Last-Modified和ETag以及Apache和Nginx中的配置
- python之twisted模块安装
- PHP面向对象知识点
- ASP.NET Core 2.0 : 五.服务是如何加载并运行的, Kestrel、配置与环境
- 深度学习中Xavier初始化
- [Java算法分析与设计]--顺序栈的实现
- 客户端和浏览器都不能连接SVN服务器
- vs2017创建.net core 应用程序,发布到Linux
- UVa 12657 Boxes in a Line(数组模拟双链表)
- python中的注释,输入输出和编码及文件
- Spring Boot(5) 集成Hibernate 日志配置
- STL中的内存与效率
- centos安装telnet