求递推序列的第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;

}