Luogu

分析

为了方便我们先令 $y$ 等于 $x + 1$，则 $S_k(x) = \sum_{i = 0}^{y - 1} i ^ k$。

根据伯努利数的结论有
$$
S_k(y) = \frac{1}{k + 1} \sum_{i = 0}^k {k + 1 \choose i} B_i y^{k + 1 - i}
$$
则答案为
$$
\sum_{k = 0}^n \frac{a_k}{k + 1} \sum_{i = 0}^k {k + 1 \choose i} B_i y ^ {k + 1 - i}
$$
稍作变形得到
$$
\sum_{k = 0}^n \frac{a_k}{k + 1} \sum_{i = 0}^k {k + 1 \choose i + 1} B_{k - i} y ^ {i + 1}
$$
交换求和号并拆掉组合数
$$
\sum_{i = 0}^k \frac{y ^ {i + 1}}{(i + 1)!} \sum_{k = i}^n a_k k! \frac{B_{k - i}}{(k - i)!}
$$
后面是差卷积的形式，翻转后一遍 NTT 即可。

然而 $y = x + 1$，考虑把求出的多项式改写为关于 $x$ 的形式。这相当于已知 $\sum_{i \geq 0} f_i x ^ i$，求 $\sum_{i \geq 0} f_i (x + 1) ^ i$。

用二项式定理拆开
$$
\sum_{i = 0}^{n + 1} f_i \sum_{j = 0}^i {i \choose j} x^j
$$
交换求和号并拆掉组合数
$$
\sum_{j = 0}^{n + 1} \frac{x ^ j}{j!} \sum_{i = j}^n i! f_i \frac{1}{(i - j)!}
$$
后面同样是差卷积的形式，翻转后一遍 NTT 即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 524288 + 10;
const int mod = 998244353;
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) c = 1ll * c * a % mod;
    return c;
}

int r[N];
void NTT(int *A, int n, int op) {
    for (int i = 0; i < n; ++i) if (i < r[i]) swap(A[i], A[r[i]]);
    for (int i = 1; i < n; i <<= 1) {
        int rot = qpow(op == 1 ? 3 : 332748118, (mod - 1) / (i << 1));
        for (int j = 0; j < n; j += i << 1)
            for (int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % mod) {
                int x = A[j + k], y = 1ll * w * A[j + k + i] % mod;
                A[j + k] = (x + y) % mod, A[j + k + i] = (x - y + mod) % mod;
            }
    }
    if (op == -1) {
        int inv = qpow(n, mod - 2);
        for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod;
    }
}
int NTT_init(int n) {
    int lim = 1, l = 0;
    for (; lim < n; lim <<= 1, ++l);
    for (int i = 0; i < lim; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    return lim;
}
void PolyInv(int *F, int *G, int n) {
    static int A[N], B[N];
    if (n == 1) { G[0] = qpow(F[0], mod - 2); return; }
    PolyInv(F, G, n >> 1);
    for (int i = 0; i < n; ++i) A[i] = F[i], B[i] = G[i];
    int lim = NTT_init(n << 1);
    NTT(A, lim, 1), NTT(B, lim, 1);
    for (int i = 0; i < lim; ++i) A[i] = 1ll * A[i] * B[i] % mod * B[i] % mod;
    NTT(A, lim, -1);
    for (int i = 0; i < n; ++i) G[i] = (2ll * G[i] - A[i] + mod) % mod;
    for (int i = 0; i < lim; ++i) A[i] = B[i] = 0;
}

int n, a[N];
int fac[N], ifac[N];
int B[N], F[N], G[N];

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

int main() {
    n = read(); init(n + 1);
    for (int i = 0; i <= n; ++i) a[i] = read();
    for (int i = 0; i <= n; ++i) F[i] = ifac[i + 1];
    int lim = 1; for (; lim <= n; lim <<= 1);
    PolyInv(F, B, lim);
    for (int i = 0; i <= n; ++i) F[i] = 1ll * a[i] * fac[i] % mod;
    for (int i = 0; i <= n; ++i) G[i] = B[i];
    reverse(G, G + n + 1);
    lim = NTT_init(n << 1 | 1);
    NTT(F, lim, 1), NTT(G, lim, 1);
    for (int i = 0; i < lim; ++i) G[i] = 1ll * F[i] * G[i] % mod;
    NTT(G, lim, -1);
    for (int i = 0; i < lim; ++i) F[i] = 0;
    for (int i = 0; i <= n; ++i) F[i + 1] = 1ll * ifac[i + 1] * G[n + i] % mod;
    lim = NTT_init((n + 1) << 1 | 1);
    for (int i = 0; i < lim; ++i) G[i] = 0;
    for (int i = 0; i <= n + 1; ++i) F[i] = 1ll * F[i] * fac[i] % mod;
    for (int i = 0; i <= n + 1; ++i) G[i] = ifac[i];
    reverse(G, G + n + 2);
    NTT(F, lim, 1), NTT(G, lim, 1);
    for (int i = 0; i < lim; ++i) F[i] = 1ll * F[i] * G[i] % mod;
    NTT(F, lim, -1);
    for (int i = 0; i <= n + 1; ++i) F[i] = 1ll * F[n + 1 + i] * ifac[i] % mod;
    for (int i = 0; i <= n + 1; ++i) printf("%d%c", F[i], " \n"[i == n + 1]);
    return 0;
}