题解

核心思路

题目要求计算求和公式 $\sum_{i=0}^{\lfloor \frac{n}{m-1} \rfloor} \binom{n+i}{m \cdot i} \mod p$。直接计算组合数会因 $n$ 过大（可达 $10^{18}$）而不可行，因此需要通过组合数学推导+线性递推+快速倍增的方法求解。

关键推导

1. 生成函数分析： 原求和的生成函数为 $F_m(x) = \frac{(1-x)^{m-1}}{(1-x)^m - x^{m-1}}$。该生成函数的分母对应线性递推关系的特征多项式，分子对应初始条件相关的多项式。

2. 线性递推关系： 由生成函数可得递推式：

   $$S(n) = \sum_{k=1}^m a_k \cdot S(n-k) \quad (n \geq m) $$

   其中 $S(n)$ 为原求和公式的结果，$a_k$ 为递推系数，可通过组合数和符号计算得出：

   • 当 $1 \leq k \leq m-2$ 时，$a_k = \binom{m}{k} \cdot (-1)^{k+1} \mod p$；
   • 当 $k = m-1$ 时，$a_{m-1} = \left(1 + m \cdot (-1)^m\right) \mod p$；
   • 当 $k = m$ 时，$a_m = (-1)^{m+1} \mod p$。

3. 初始条件： 由于 $S(t) = \sum_{i=0}^{\lfloor \frac{t}{m-1} \rfloor} \binom{t+i}{m \cdot i}$，当 $t < m-1$ 时，$\lfloor \frac{t}{m-1} \rfloor = 0$，故 $S(t) = 1$；当 $t = m-1$ 时，$\lfloor \frac{t}{m-1} \rfloor = 1$，故 $S(t) = 2$。

4. 快速倍增法： 递推式的阶数为 $m$（最大 5000），$n$ 可达 $10^{18}$，需用多项式快速幂（快速倍增） 计算第 $n$ 项，时间复杂度 $O(m^2 \log n)$。

解题步骤

1. 预处理组合数：计算 $\binom{m}{k} \mod p$（$0 \leq k \leq m$），用于递推系数计算。
2. 计算递推系数：根据上述公式计算 $a_1 \sim a_m$。
3. 初始化初始值：设置 $S(0) \sim S(m-1)$。
4. 多项式快速幂：计算 $x^n \mod P(x)$（$P(x)$ 为特征多项式），得到系数数组 $q$。
5. 计算结果：通过 $q$ 与初始值的线性组合得到 $S(n) \mod p$。

C++ 代码

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

vector<ll> mult_mod(const vector<ll>& A, const vector<ll>& B, const vector<ll>& a, int m, ll p) {
    vector<ll> C(2 * m - 1, 0);
    for (int i = 0; i < m; ++i) {
        if (A[i] == 0) continue;
        for (int j = 0; j < m; ++j) {
            C[i + j] = (C[i + j] + A[i] * B[j]) % p;
        }
    }
    for (int t = 2 * m - 2; t >= m; --t) {
        if (C[t] == 0) continue;
        for (int k = 1; k <= m; ++k) {
            int pos = t - k;
            C[pos] = (C[pos] + C[t] * a[k]) % p;
        }
        C[t] = 0;
    }
    vector<ll> res(m, 0);
    for (int i = 0; i < m; ++i) {
        res[i] = (C[i] % p + p) % p;
    }
    return res;
}

vector<ll> pow_mod(ll n, const vector<ll>& a, int m, ll p) {
    vector<ll> res(m, 0);
    res[0] = 1 % p;
    vector<ll> base(m, 0);
    if (m >= 2) base[1] = 1 % p;
    while (n > 0) {
        if (n % 2 == 1) {
            res = mult_mod(res, base, a, m, p);
        }
        base = mult_mod(base, base, a, m, p);
        n /= 2;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    int m;
    ll p;
    cin >> n >> m >> p;
    if (p == 1) {
        cout << 0 << endl;
        return 0;
    }
    vector<vector<ll>> comb(m + 1, vector<ll>(m + 1, 0));
    comb[0][0] = 1 % p;
    for (int i = 1; i <= m; ++i) {
        comb[i][0] = 1 % p;
        comb[i][i] = 1 % p;
        for (int j = 1; j < i; ++j) {
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % p;
        }
    }
    vector<ll> a(m + 1, 0);
    for (int k = 1; k <= m - 2; ++k) {
        ll sign = ((k + 1) % 2 == 0) ? 1 : -1;
        ll val = (comb[m][k] * sign) % p;
        if (val < 0) val += p;
        a[k] = val;
    }
    ll sign_m = (m % 2 == 0) ? 1 : -1;
    ll term = ((ll)m % p) * sign_m % p;
    a[m - 1] = (1 + term) % p;
    if (a[m - 1] < 0) a[m - 1] += p;
    ll sign_m_plus_1 = ((m + 1) % 2 == 0) ? 1 : -1;
    a[m] = sign_m_plus_1 % p;
    if (a[m] < 0) a[m] += p;
    vector<ll> S(m, 0);
    for (int t = 0; t < m - 1; ++t) {
        S[t] = 1 % p;
    }
    S[m - 1] = 2 % p;
    if (n < m) {
        cout << (S[n] % p + p) % p << endl;
        return 0;
    }
    vector<ll> q = pow_mod(n, a, m, p);
    ll ans = 0;
    for (int k = 0; k < m; ++k) {
        ans = (ans + q[k] * S[k]) % p;
    }
    ans = (ans % p + p) % p;
    cout << ans << endl;
    return 0;
}

代码解释

1. 组合数预处理：使用动态规划计算 $\binom{m}{k} \mod p$，避免溢出。
2. 递推系数计算：根据推导公式计算 $a_1 \sim a_m$，确保系数为非负。
3. 多项式乘法模：实现多项式乘法并对特征多项式取模，用于降次。
4. 多项式快速幂：通过二进制快速幂计算 $x^n \mod P(x)$，高效得到递推所需的系数。
5. 结果计算：通过系数与初始值的线性组合得到最终答案，确保结果在模 $p$ 下非负。

该方法高效处理了大 $n$ 和大 $m$ 的情况，时间复杂度为 $O(m^2 \log n)$，可满足所有测试点要求。