1126 求递推序列的第N项 

基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题

 收藏

 关注

输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)

输出f(n)的值。

3 -1 5

6

找规律的题

#include <bits\stdc++.h>

using namespace std;

typedef long long ll;

int f[10000];  // 存递推项。

int v[10][10]; // v[i][j]表示 f[k-1]和f[k]出现的位置，第二次出现就找到了循环节了。

int main() {

    int a,b,n;

    cin >> a >> b >> n;

    int round ;  // 循环节长度

    f[1] = f[2] = 1;

    v[1][1] = 1;  // 1，1连续出现的位置是1

    int start;    // 循环节开始的位置-1。

    for(int i = 3;; i++){

        f[i] = ((a*f[i-1] + b*f[i-2])%7+7)%7;  // 让f[i]变成成正数。

//        cout << "i: " << i << " f: " << f[i] << endl;

        if(i == n){

            cout << f[i] << endl; // 如果求出循环节之前求出了答案，直接输出。

            return 0;

        }

        if(v[f[i-1]][f[i]] == 0){

            v[f[i-1]][f[i]] = i-1;  // f[i-1],f[i]第一次出现

        }else{

            // 第二次出现

            round = i-1-v[f[i-1]][f[i]];   // 循环节长度

            start = v[f[i-1]][f[i]]-1;   // 循环节开始的位置-1。

            break;

        }

    }

    n -= start;  // 减去不在循环节之内的部分。

    n = n % round;  // 求出n在循环节中的位置。

    //已知的循环节从 start+1 - start+round。

    if(n == 0) cout << f[start+round] << endl;

    else cout << f[start+n] << endl;

    return 0;

}