<兔农>题解

代码如下

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long ll;

ll p;   // 全局模数，先声明

struct Matrix {
    ll a[3][3];
    Matrix() {
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                a[i][j] = 0;
    }
    Matrix operator*(const Matrix& other) const {
        Matrix res;
        for (int i = 0; i < 3; ++i)
            for (int k = 0; k < 3; ++k)
                if (a[i][k])
                    for (int j = 0; j < 3; ++j)
                        res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % p;
        return res;
    }
};

Matrix mat_pow(Matrix base, ll exp) {
    Matrix res;
    for (int i = 0; i < 3; ++i) res.a[i][i] = 1;
    while (exp) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

int main() {
    ll n, k;
    cin >> n >> k >> p;
    if (n == 1 || n == 2) {
        cout << 1 % p << endl;
        return 0;
    }

    // 状态：(prev_modk, cur_modk) -> 首次出现的月份（cur 对应的月份）
    unordered_map<ll, ll> state_map;
    vector<ll> month_fp;   // 每月的模 p 值，下标从 1 开始
    vector<ll> month_delta; // 每月的 delta（从第 3 个月开始，存 delta_i）
    month_fp.push_back(0); // 占位
    month_fp.push_back(1 % p);
    month_fp.push_back(1 % p);
    month_delta.push_back(0); // 占位
    month_delta.push_back(0);
    month_delta.push_back(0);

    ll a_k = 1, b_k = 1;   // 前两个月的模 k 值
    ll a_p = 1 % p, b_p = 1 % p;
    ll cur_month = 2;
    state_map[1 * k + 1] = 2;

    ll start = -1, cycle_len = -1;

    while (true) {
        cur_month++;
        ll sum_k = (a_k + b_k) % k;
        ll delta = (sum_k == 1) ? 1 : 0;
        ll c_k = (sum_k - delta + k) % k;
        ll c_p = (a_p + b_p - delta) % p;
        if (c_p < 0) c_p += p;

        month_fp.push_back(c_p);
        month_delta.push_back(delta);

        ll state = b_k * k + c_k;
        auto it = state_map.find(state);
        if (it != state_map.end()) {
            start = it->second;
            cycle_len = cur_month - start;
            break;
        }
        state_map[state] = cur_month;

        a_k = b_k; b_k = c_k;
        a_p = b_p; b_p = c_p;
    }

    // 如果 n 在循环开始之前
    if (n <= cur_month) {
        cout << month_fp[n] << endl;
        return 0;
    }

    // 计算从 start 到 start+cycle_len-1 的累积转移矩阵
    Matrix total;
    for (int i = 0; i < 3; ++i) total.a[i][i] = 1;
    for (ll t = start + 1; t <= start + cycle_len; ++t) {
        Matrix M;
        M.a[0][0] = 1; M.a[0][1] = 1; M.a[0][2] = (p - month_delta[t]) % p;
        M.a[1][0] = 1;
        M.a[2][2] = 1;
        total = M * total;   // 左乘顺序
    }

    ll full_cycles = (n - start) / cycle_len;
    ll rem = (n - start) % cycle_len;

    Matrix power = mat_pow(total, full_cycles);

    // 初始状态向量 (f_{start}, f_{start-1}, 1)
    ll f_start = month_fp[start];
    ll f_prev = month_fp[start - 1];
    ll vec[3] = {f_start, f_prev, 1};

    ll new_vec[3] = {0};
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            new_vec[i] = (new_vec[i] + power.a[i][j] * vec[j]) % p;

    // 再应用剩余步数的转移
    for (ll t = start + 1; t <= start + rem; ++t) {
        ll new_f = (new_vec[0] + new_vec[1] - month_delta[t]) % p;
        if (new_f < 0) new_f += p;
        new_vec[2] = 1;
        new_vec[1] = new_vec[0];
        new_vec[0] = new_f;
    }

    cout << new_vec[0] << endl;

    return 0;