数列（循环节）

题意

有一个整数数列\(a_0, a_1, a_2, a_3 \dots\)

该数列的前两项\(a_0, a_1\)的具体值已知，其它项可以通过如下递推式求出：

• \(a_n = p \times a_{n−1} + q \times a_{n−2}(n \geq 2)\)

给定一个可能非常大的正整数\(N\)和两个不太大的正整数\(M, K\)，请你分别计算并输出\(a_{N+1}, a_{N+2}, \dots, a_{N+K}\)对\(M\)取模的值。

题目链接：https://www.acwing.com/problem/content/4584/

数据范围

\(0 < a_0, a_1, p, q \leq 32693\)
\(0 < M \leq 3 \times 10^3\)
\(0 < K \leq 10^4\)
\(0 < N < 10^{10^6}\)

思路

首先我们观察到\(M\)的范围较小，只有\(3 \times 10^3\)，因此数列中的数最多有\(3 \times 10^3\)个取值。

\(N\)特别大，这种题目的典型套路是分析循环节。

那么什么时候才会出现循环呢？如果\(a_{i-1}\)和\(a_i\)在之前出现过，即存在\(j < i\)满足\(a_{j-1} = a_{i-1}\)并且\(a_j = a_i\)。那么就出现循环了。其中循环节的长度为\(r = i-j\)。

因此，我们只需要计算出\(N\)位于循环节的哪个位置即可，即：\((n - (j - 1)) \% r = n \% r - (j - 1) \% r\)。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e7 + 10, M = 3010;

int a[N], p, q;
int m, k;
int id[M][M];
string n;

int main()
{
    cin >> a[0] >> a[1] >> p >> q >> m >> k >> n;
    a[0] %= m, a[1] %= m;
    id[a[0]][a[1]] = 1;
    int ed, st;
    for(int i = 2; i < N; i ++) {
        a[i] = (a[i - 1] * p % m + a[i - 2] * q % m) % m;
    }
    for(int i = 2; i < N; i ++) {
        if(id[a[i - 1]][a[i]]) {
            ed = i - 2;
            st = id[a[i - 1]][a[i]] - 1;
            break;
        }
        id[a[i - 1]][a[i]] = i;
    }
    int len = ed - st + 1;
    if(n.size() <= 7) {
        int num = 0;
        for(int i = 0; i < n.size(); i ++) {
            num = num * 10 + n[i] - '0';
        }
        for(int i = 1; i <= k; i ++) {
            cout << a[num + i] << '\n';
        }
    }
    else {
        int num = 0;
        for(int i = 0; i < n.size(); i ++) {
            num = (num * 10 % len + n[i] - '0') % len;
        }
        int r = (num - st % len + len) % len;
        for(int i = st + r + 1; i <= st + r + k; i ++) {
            cout << a[i] << '\n';
        }
    }
    return 0;
}