题解 | #智乃酱的前缀和与差分#

以下是此题代码 #include<bits/stdc++.h> using namespace std;

const int MOD = 998244353; const int G = 3;

int modpow(int a, int e) { int res = 1; while (e) { if (e & 1) res = 1LL * res * a % MOD; a = 1LL * a * a % MOD; e >>= 1; } return res; }

void ntt(vector& a, bool inv) { int n = a.size(); for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { int wlen = modpow(G, (MOD - 1) / len); if (inv) wlen = modpow(wlen, MOD - 2); for (int i = 0; i < n; i += len) { int w = 1; for (int j = 0; j < len / 2; j++) { int u = a[i + j]; int v = 1LL * a[i + j + len / 2] * w % MOD; a[i + j] = (u + v) % MOD; a[i + j + len / 2] = (u - v + MOD) % MOD; w = 1LL * w * wlen % MOD; } } } if (inv) { int inv_n = modpow(n, MOD - 2); for (int& x : a) x = 1LL * x * inv_n % MOD; } }

vector multiply(vector a, vector b) { int n = 1; while (n < a.size() + b.size()) n <<= 1; a.resize(n); b.resize(n); ntt(a, false); ntt(b, false); for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * b[i] % MOD; ntt(a, true); return a; }

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int n;
long long k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

if (k == 0) {
    for (int i = 0; i < n; i++) cout << a[i] % MOD << " ";
    return 0;
}

vector<int> b(n);
if (k > 0) {
    b[0] = 1;
    for (int j = 1; j < n; j++) {
        b[j] = 1LL * b[j-1] * ((k + j - 1) % MOD) % MOD;
        b[j] = 1LL * b[j] * modpow(j, MOD - 2) % MOD;
    }
} else {
    long long d = -k;
    b[0] = 1;
    for (int j = 1; j < n && j <= d; j++) {
        b[j] = 1LL * b[j-1] * ((d - j + 1) % MOD) % MOD;
        b[j] = 1LL * b[j] * modpow(j, MOD - 2) % MOD;
    }
    for (int j = 1; j < n; j++) {
        if (j & 1) b[j] = (MOD - b[j]) % MOD;
    }
}

vector<int> conv = multiply(a, b);
for (int i = 0; i < n; i++) {
    cout << conv[i] % MOD << " ";
}

return 0;

} 题解不唯一