51nod1126 求递推序列的第N项

 求递推序列的第N项

有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

给出A，B和N，求f(n)的值。

Input输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9) Output输出f(n)的值。 Sample Input

3 -1 5

Sample Output

6

原来想直接暴力 后来发现n是1e9 内存显然不够 显然不能暴力。

用AB代进去想看看是不是能找到什么规律推出一个什么公式来 发现好像也不行

查了题解发现其实大有玄机。

因为每次f都要%7，所以f【n】只能是0-6的数，当然f【n-1】和f【n-2】也是

所以f的值最多只可能有7*7=49种可能 会循环起来【原因似懂非懂】

最开始一直错 是因为没发现负数的取余 他要求要非负【虽然题目好像没说？】

结果反正要先取模再加7

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;

int a, b, n;
int f[55];

int main()
{
    cin>> a>> b>> n;
        memset(f, 0, sizeof(f));
        //if(a==0&&b==0&&n==0) break;
        f[1] = 1;
        f[2] = 1;
        int i;
        for(i = 3; i <= 49; i++){
            f[i] = (a * f[i - 1] + b * f[i - 2]) % 7 + 7;
            f[i] = f[i] % 7;
            if(f[i] == 1 && f[i - 1] == 1) break;
        }
        i -= 2;
        f[0] = f[i];
        cout<< f[n % i]<< endl;
    return 0;
}