题解：P16782 ⌈Xzy OI R1 T4⌋ 吃吃冰

· · 题解

题面写的何意味，下面让 n 减 1。

设 F=\displaystyle\sum_{i=0}^mx^i=\dfrac{x^{m+1}-1}{x-1}，G=F^n，则走 n 步到达 k 的方案数为 [x^k]F^n。

考虑递推 G 的系数，有 G'=nF'F^{n-1}，即 FG'=nF'G，比较 x^{k-1} 项的系数，有：

\sum_{i=0}^kig_i\cdot f_{k-i}=n\sum_{i=0}^{k-1}g_i\cdot(k-i)f_{k-i}\\ g_k=\dfrac{1}{kf_0}\sum_{i=0}^{k-1}(n(k-i)-i)g_if_{k-i}

有 f_k=[k\le m]，因此：

g_k=\dfrac1k\sum_{i=\max(0,k-m)}^{k-1}(nkg_i-(n+1)ig_i)

边界为 g_0=1，可以前缀和优化，复杂度为 \mathcal O(nm)。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll; const int N = 1e6 + 5, p = 998244353; char buf[N], *p1, *p2;
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N, stdin), p1 == p2) ? EOF : *p1++)
il void rd(int &x) { x = 0; char c = 0; bool f = 0; while (c < '0' || c > '9') c = gc, f |= c == '-'; while (c >= '0' && c <= '9') x = x * 10 - '0' + c, c = gc; if (f) x = -x; }
int n, m, l, a[N], iv[N], g[N], sg[N], sig[N];
int main() {
    rd(n), rd(m), l = (--n) * m; for (int i = 0; i <= l; i++) rd(a[i]), a[i] += a[i] < 0 ? p : 0;
    g[0] = sg[0] = 1; for (int i = 1, Sg, Sig; i <= l; i++) {
        iv[i] = i == 1 ? 1 : ll(p - p / i) * iv[p % i] % p;
        Sg = sg[i - 1] - (i > m ? sg[i - m - 1] : 0) + p;
        Sig = sig[i - 1] - (i > m ? sig[i - m - 1] : 0) + p;
        g[i] = (((ll)n * i % p * Sg - (n + 1ll) * Sig) % p + p) * iv[i] % p;
        sg[i] = sg[i - 1] + g[i], sg[i] -= sg[i] >= p ? p : 0;
        sig[i] = (sig[i - 1] + (ll)i * g[i]) % p;
    } int ans = 0;
    for (int i = 0; i <= l; i++) ans = (ans + (ll)a[i] * g[i]) % p; cout << ans;
}

所以出题人真的见过 poly 题吗。