| A | B | C | D | E |
| F | G | H | I | J |
| K | L | M | N | O |
| P | Q | R | S | T |
| U | V | W | X |
$M $ 以下の非負整数からなる長さ $N$ の整数列のうち、総和が $S$ であるものの個数 ${\rm mod}$ $998244353$ を求めよ
$1 \le N,M,S \le 2 \times 10^5$
本番解法: さすがに有名問題。 $M $ を超える要素の個数 $k$ を固定して、包除原理。
https://atcoder.jp/contests/fps-24/submissions/70655443
FPS 解法はこんな感じ。
$[x^S] (1+x+\dots+x^M)^N$
$\displaystyle =[x^S] \frac{(1-x^{M+1})^N}{(1-x)^N}$
これを分母と分子に切り分けて扱うことで求める。
分子の $x^k$ につく係数は $k$ が $M+1$ の倍数でないとき $0$ 、 $k$ が $M+1$ の倍数であるとき $l=k/(M+1)$ として $(-1)^l \times C(N,l)$ 。
(分母の影響を受けた結果) $x^S$ につく係数への寄与を求めたいが、これは $(1+x+x^2+\dots)^N$ の $x^{S-k}$ につく係数を考えればよく、 $C(S-k+N-1,S-k)$ 倍として表現される。
組み合わせ論的には $S-k$ 個の区別できない球を $N$ 箱に分ければ ok 。
https://atcoder.jp/contests/fps-24/submissions/70852859
包除通らず導出できるのはすごい楽かもしれない。
初めて公式解説見ずに FPS 解法導出できた。洗脳始まってきてるなぁ
