P10286 题解

· · 题解

upd on 2024.7.31：做法太唐，重写。

根据 简单版 的柿子，我们要计算下面这个东西：

\forall 0\le i\le n,[x^i]G(F+1)^i

先 F\gets F+1。考虑引入第二元 y 用于区分不同的 i。我们只需要求出：

\begin{aligned} &[x^0]\sum_iy^iGF^ix^{-i}\\ \overset{\operatorname{rev}}{=}&[x^n]G\sum y^iF^{n-i}x^i\\ =&[x^n]GF^n\sum y^i(xF^{-1})^i\\ =&[x^n]\frac{GF^n}{1-yxF^{-1}}\\ \end{aligned}

直接 bostan-mori 计算，时间复杂度 O(n\log^2 n)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 998244353;

using namespace polynomial; // By R_i.

typedef vector<poly<int>> polyv;

inline 
polyv operator * (const polyv &f, const polyv &g) {
    int n = f.size(), m = g.size(), x = f[0].size(), y = g[0].size();
    poly<int> a(n * (x + y - 1)), b(m * (x + y - 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < x; j++) a[i * (x + y - 1) + j] = f[i][j];
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < y; j++) b[i * (x + y - 1) + j] = g[i][j];
    }
    a *= b; polyv res(n + m - 1, poly<int>(x + y - 1));
    for (int i = 0; i < n + m - 1; i++) {
        for (int j = 0; j < x + y - 1; j++) res[i][j] = a[i * (x + y - 1) + j];
    }
    return res;
}

poly<int> bostan_mori(int n, polyv f, polyv g) {
    if (!n) return f[0] * inv(g[0]);
    if (n + 1 < f.size()) f.resize(n + 1);
    if (n + 1 < g.size()) g.resize(n + 1);
    polyv h = g;
    for (int i = 1; i < h.size(); i += 2) h[i] = -h[i];
    f = f * h, g = g * h; polyv a, b;
    for(int i = n & 1; i < f.size(); i += 2) a.push_back(f[i]);
    for(int i = 0; i < g.size(); i += 2) b.push_back(g[i]);
    return bostan_mori(n >> 1, a, b);
}

const int MAXN = 1e5 + 10;

int fac[MAXN], ifac[MAXN], tk[MAXN], p2[MAXN];

inline 
void init(int n) {
    *fac = 1;
    for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for (int i = n; i; i--) ifac[i - 1] = (ll)ifac[i] * i % mod;
    tk[1] = 1;
    for (int i = 2; i <= n; i++) tk[i] = qpow(i, i - 2);
    *p2 = 1;
    for (int i = 1; i <= n; i++) p2[i] = (p2[i - 1] << 1) % mod;
}

int n, k, ans, t = 1, a[MAXN];

poly<int> f, g; polyv p, q;

int main() {
    scanf("%d%d", &n, &k), ++n, init(n), f.resize(n), g.resize(n);
    for (int i = 0; i < n; i++) g[i] = (ll)t * ifac[i] % mod, t = (ll)t * p2[i + 2 - k] % mod;
    for (int i = 0; i < n; i++) f[i] = (ll)tk[i] * ifac[i] % mod;
    g *= inv(exp(f)), g.resize(n), f[0]++;
    g = g * pow(f, n - 1), f = inv(f) >> 1;
    for (int i = 0; i < n; i++) {
        p.push_back(vector<int>({ g[i], 0 }));
        q.push_back(vector<int>({ !i, mod - f[i] }));
    }
    g = bostan_mori(n - 1, p, q), g.resize(n), g.reverse();
    for (int i = 0; i < n; i++) g[i] = (ll)g[i] * fac[i] % mod;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), ans = (ans + (ll)a[i] * g[i] % mod) % mod;
    printf("%lld", ans);
}