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

williamwei · 2025-11-08 20:57:16 · 题解

来一篇只用组合意义，不需要找规律的题解。

根据题面，先写出这两个多项式 f, g 进行一次运算后的结果 f', g' 的每一项：

注意到会导致 f, g 被交换，直接算比较麻烦，使用一个在此情况下的常用 Trick：将两次运算分为一组处理，如果有一个剩余的运算则暴力计算。这样每次不会产生交换。

通过代入计算可以得知多项式 f, g 进行两次运算后的 F, G 的每一项：

观察这个式子，考虑一组运算后系数的组合意义：以 f \to F 为例，有一个【势能台阶】，位于 i 这个位置的元素具有 f_i 的势能。每次可以不动，也可以向下走 2 步到达高度为 i - 2 的位置，其势能乘上 -(i + 1)(i + 2)。最后 F_i 即为每一个不同的下台阶方案最终到达 i 的势能和。

为了方便推导，反过来思考，考虑从最终位置向上走：假设有 k = \lfloor \dfrac{n}{2} \rfloor 组运算，考虑每一个位置 i，在 k 次上楼梯的操作中向上 j 次，其势能贡献为 f_{i + 2j} \times \prod \limits_{l = 0}^{j - 1} -(i + 2l + 1)(i + 2l + 2)（起始位置的势能乘路上的势能乘积），简化一下变为 f_{i + 2j} \times \prod \limits_{l = i + 1}^{i + 2j} l \times (-1)^j。上楼梯的方案数为 \dbinom{k}{j}。

所以 F_i = \sum \limits_{i \le i + 2j \le m} (-1)^j \times \dbinom{k}{j}f_{i + 2j} \times \prod \limits_{l = i + 1}^{i + 2j} l。

最后考虑有剩余运算的情况（n 为奇数），暴力模拟即可。

预处理逆元，因为 k 比较大，所以需要预处理组合数。时间复杂度 \mathcal{O}(m^2)。

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 5000 + 10;
const int mod = 1e9 + 7;
int n, m, f[maxn], g[maxn], F[maxn], G[maxn], c[maxn], fac[maxn], inv[maxn];
int qpow(int a, int b) {
    int res = 1; for (; b; b >>= 1, a = (ll)a * a % mod)
        if (b & 1) res = (ll)res * a % mod; return res;
}
void calc(int* f, int* F) {
    for (int i = 0; i <= m; i++)
        for (int j = 0; i + (j << 1) <= m && j <= n; j++)
            F[i] = (F[i] + (ll)(j & 1 ? -1 : 1) * f[i + (j << 1)] * c[j] % mod * fac[i + (j << 1)] % mod * inv[i]) % mod;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m; fac[0] = inv[0] = 1;
    for (int i = 0; i <= m; i++) cin >> f[i];
    for (int i = 0; i <= m; i++) cin >> g[i];
    for (int i = 1; i <= m; i++) fac[i] = (ll)fac[i - 1] * i % mod, inv[i] = qpow(fac[i], mod - 2);
    // 处理奇数情况：单独进行一次操作
    if (n & 1) {
        for (int i = 0; i <= m; i++) F[i] = (g[i] + (ll)(i + 1) * g[i + 1]) % mod,
            G[i] = (f[i] - (ll)(i + 1) * f[i + 1]) % mod;
        for (int i = 0; i <= m; i++) f[i] = F[i], g[i] = G[i], F[i] = G[i] = 0;
    } n >>= 1;
    // 预处理组合数 C(n, j) = n * (n - 1) * ... * (n - j + 1) / j!
    for (int i = 0; i <= m; i++) {
        c[i] = inv[i];
        for (int j = n; j > n - i; j--) c[i] = (ll)c[i] * j % mod;
    } // 计算经过 k 组操作后的 F 和 G
    calc(f, F); calc(g, G);
    for (int i = 0; i <= m; i++) cout << (F[i] + mod) % mod << ' '; cout << '\n';
    for (int i = 0; i <= m; i++) cout << (G[i] + mod) % mod << ' '; cout << '\n';
    return 0;
}