题解：P14461 【MX-S10-T2】『FeOI-4』青年晚报

· · 题解

P14461 【MX-S10-T2】『FeOI-4』青年晚报 题解

题目大意

给定两个初始的 m 次多项式 F_0(x) 和 G_0(x)，以及递推关系：

\begin{aligned} F_i(x) &= G_{i-1}(x) + G_{i-1}'(x) \\ G_i(x) &= F_{i-1}(x) - F_{i-1}'(x) \end{aligned}

求经过 n 次递推后的 F_n(x) 和 G_n(x) 的各项系数，结果对 10^9+7 取模。

解题思路

关键观察

通过分析递推关系，我们发现每两次递推构成一个循环：

\begin{aligned} F_n(x) &= F_{n-2}(x) - F_{n-2}''(x) \\ G_n(x) &= G_{n-2}(x) - G_{n-2}''(x) \end{aligned}

这意味着我们可以将问题分为奇偶两种情况处理。

数学推导

设 F_n(x) = \sum_{i=0}^m a_{n,i} x^i，G_n(x) = \sum_{i=0}^m b_{n,i} x^i。

经过数学推导，我们得到：

当 n 为偶数时（n = 2k）：

\begin{aligned} a_{2k,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \cdot \frac{(i+2j)!}{i!} \cdot a_{0,i+2j} \\ b_{2k,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \cdot \frac{(i+2j)!}{i!} \cdot b_{0,i+2j} \end{aligned}

当 n 为奇数时（n = 2k+1）：

\begin{aligned} a_{2k+1,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \left[ \frac{(i+2j)!}{i!} b_{0,i+2j} + \frac{(i+2j+1)!}{i!} b_{0,i+2j+1} \right] \\ b_{2k+1,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \left[ \frac{(i+2j)!}{i!} a_{0,i+2j} - \frac{(i+2j+1)!}{i!} a_{0,i+2j+1} \right] \end{aligned}

复杂度

代码实现


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 5100;

int n, m;
int f[N], g[N], F[N], G[N];
int fac[N], facinv[N], inv[N];

// 模运算优化函数
void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}
void mul(int &x, int y) {
    x *= y;
    if (x >= mod) x %= mod;
}
void sub(int &x, int y) {
    x -= y;
    if (x < 0) x += mod;
    if (x >= mod) x -= mod;
}

// 快速幂
int qp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和逆元
void init() {
    fac[0] = facinv[0] = inv[1] = 1;
    for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
        facinv[i] = facinv[i - 1] * inv[i] % mod;
    }
}

// 计算组合数 C(n,m)
int C(int n, int m) {
    if (m < 0 || m > n) return 0;
    int res = 1;
    for (int i = 0; i < m; i++) mul(res, n - i);
    mul(res, facinv[m]);
    return res;
}

int val[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    init();
    for (int i = 0; i <= m; i++) cin >> f[i];
    for (int i = 0; i <= m; i++) cin >> g[i];

    if (n & 1) {
        // 奇数情况: n = 2k+1
        int k = (n - 1) / 2;
        for (int i = 0; i <= m / 2; i++)
            val[i] = (i & 1) == 0 ? C(k, i) : -C(k, i);

        for (int i = 0; i <= m; i++) {
            int sumf = 0, sumg = 0;
            for (int j = 0; i + 2 * j <= m; j++) {
                int tp1 = i + 2 * j, tp2 = i + 2 * j + 1;
                if (tp1 <= m) {
                    add(sumf, val[j] * fac[tp1] % mod * facinv[i] % mod *
                                  g[tp1] % mod);
                    add(sumg, val[j] * fac[tp1] % mod * facinv[i] % mod *
                                  f[tp1] % mod);
                }
                if (tp2 <= m) {
                    add(sumf, val[j] * fac[tp2] % mod * facinv[i] % mod *
                                  g[tp2] % mod);
                    sub(sumg, val[j] * fac[tp2] % mod * facinv[i] % mod *
                                  f[tp2] % mod);
                }
            }
            F[i] = sumf;
            G[i] = sumg;
        }
    } else {
        // 偶数情况: n = 2k
        int k = n / 2;
        for (int i = 0; i <= m / 2; i++)
            val[i] = (i & 1) == 0 ? C(k, i) : -C(k, i);

        for (int i = 0; i <= m; i++) {
            int sumf = 0, sumg = 0;
            for (int j = 0; i + 2 * j <= m; j++) {
                int tp = i + 2 * j;
                add(sumf,
                    val[j] * fac[tp] % mod * facinv[i] % mod * f[tp] % mod);
                add(sumg,
                    val[j] * fac[tp] % mod * facinv[i] % mod * g[tp] % mod);
            }
            F[i] = sumf;
            G[i] = sumg;
        }
    }

    for (int i = 0; i <= m; i++) cout << F[i] << ' ';
    cout << '\n';
    for (int i = 0; i <= m; i++) cout << G[i] << ' ';
    cout << '\n';

    return 0;
}