HDOJ 1005 Number Sequence

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
2
5

对于公式 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<iostream>
#include<stdio.h>
using namespace std;
int f[100000005];
int main()
{
    int a,b,n,i,j;

    f[1]=1;f[2]=1;
    while(scanf("%d%d%d",&a,&b,&n))
    {
        int s=0;//记录周期
        if(a==0&&b==0&&n==0) break;
        for(i=3;i<=n;i++)
        {
            f[i]=(a*f[i-1]+b*f[i-2])%7;
            for(j=2;j<i;j++)
            if(f[i-1]==f[j-1]&&f[i]==f[j])//此题可以这样做的原因就是 2个确定后就可以决定后面的
            {
                s=i-j;
                //cout<<j<<" "<<s<<" >>"<<i<<endl;
                break;
            }
            if(s>0) break;
        }
        if(s>0){

                 f[n]=f[(n-j)%s+j];
                 //cout<<"f["<<n<<"]:="<<"f["<<(n-j)%s+j<<"] "<<endl;
               }
        cout<<f[n]<<endl;

    }
    return 0;
}
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int[] a = new int[54];
            int A  = sc.nextInt();
            int B  = sc.nextInt();
            int n  = sc.nextInt();
            if(A==0&&B==0&n==0){
                return ;
            }
            a[1]=1;
            a[2]=1;
            int k=0;
            int i;
            for(i=3;i<54;i++){
                a[i] = (A*a[i-1]+B*a[i-2])%7;
                if(i>5&&a[i]==a[4]&&a[i-1]==a[3]){
                    k=i-4;
                    break;
                }
            }
            //System.out.println(k);
            if(n>2){
                System.out.println(a[(n-3)%k+3]);
            }else{
                System.out.println("1");
            }

        }
    }

}
时间: 2024-09-27 17:06:32

HDOJ 1005 Number Sequence的相关文章

acm-杭电ACM OJ 1005 Number Sequence

问题描述 杭电ACM OJ 1005 Number Sequence 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). 超过49个数之后一定会出现和之前的数组合相同的情况,这个我可以了解,但是 为什么最多经过49个数之后一定会出现周

UVa 10706:Number Sequence

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1647 原题: A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of n

UVa 10706 / POJ 1019 Number Sequence:打表及O(1)算法

10706 - Number Sequence Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1647 http://poj.org/problem?id=1019 Description A single positive integer i is giv

[ACMcoder] Number Sequence

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 co

HDOJ 1391 Number Steps(打表DP)

Problem Description Starting from point (0,0) on a plane, we have written all non-negative integers 0, 1, 2,- as shown in the figure. For example, 1, 2, and 3 has been written at points (1,1), (2,0), and (3, 1) respectively and this pattern has conti

hdu 1711 Number Sequence

点击打开链接hdu1711 思路:KMP kmp算法: 1 kmp是用来匹配字符串,只能够匹配单一的字符串 2 kmp的算法的过程:   1:假设文本串的长度为n,模式串的长度为m:   2:先例用O(m)的时间去预处理next数组,next数组的意思指的是当前的字符串匹配失败后要转到的下一个状态:   3:利用o(n)的时间去完成匹配: 3 时间复杂度为o(n+m)即o(n): 代码: #include<algorithm> #include<iostream> #include

2014 网选 5014 Number Sequence(异或)

/* 题意:a, b两个序列,规定由[0, n]区间的数! 求 a[i] ^ b[i] 的和最大! 思路:如果数字 n的二进制有x位, 那么一定存在一个数字m,使得n^m的所有二进制位 都是1,也就是由x位1!这样下去的到的值就是最大值! */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define N 100005 using namespace s

uva 10706 - Number Sequence

点击打开链接uva 10706 题目意思:    有一个数组 s[1] = 1 , s[2] = 1 2 , .......s[k] = 1....k,要求给定一个n表示数组的第几位,要求这个第几位是什么数.例如 n为1 时候是1 n为 2 时候是1 ,n 为3 时候为2 解题思路:    1:思路:预处理打表+查找                      2:题目给的数据可以发现一些规律                         s[1]:1                      

HIT 2275 Number sequence

点击打开HIT 2275 思路: 树状数组 分析: 1 题目要求的是总共的搭配方式,满足Ai < Aj > Ak.并且i j k不同 2 我们开两个树状数组,第一个在输入的时候就去更新.然后我们在去枚举Aj 同时维护第二个树状数组,对于AI来说就是在第二个树状数组里面求和 然后在通过第一个树状数组就可以求出Ak的个数,把结果相乘即可 代码: #include<cstdio> #include<cstring> #include<iostream> #incl