| 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$ の整数列 $A$ であって以下の条件を満たすものを数えよ。 ${\rm mod}$ $998244353$
- $A$ を昇順ソートした列 $B$ について、隣接する要素の偶奇が異なる。
$1 \le N,M \le 2 \times 10^5$
本番解法:
$B$ の要素は明らかに相異なるので、並べ方の自由度が $N!$ ある。このもとで $B$ を数えることにする。
$B_N-B_1$ を $N-1,N+1,N+3,\dots$ と固定。このもとで公差を「 $2$ ずつ配る」ことを考える。これは二項係数で求まる。
最後に $B_1$ の自由度ぶん係数を掛ければ ok。
https://atcoder.jp/contests/fps-24/submissions/70656350
FPS 解は以下の通り。
$B$ を数えて $N!$ 倍するところは同じ。
求めたいものは次のように書ける。
$[x^M] (1+x+x^2+\dots) \times (x+x^3+x^5+\dots)^{N-1} \times (1+x+x^2+\dots)$
$=[x^M] (1+x+x^2+\dots)^2x^{N-1}(1+x^2+x^4+\dots)^{N-1}$
$=[x^{M-N+1}] (1+x+x^2+\dots)^2(1+x^2+x^4+\dots)^{N-1}$ ... ★
$\displaystyle =[x^{M-N+1}] \frac{1}{(1-x)^2} \times \left ( \frac{1}{(1-x^2)} \right ) ^{N-1}$
ここで手が止まってしまって解説を見に行く。分母の因数分解をすれば良いらしいがまだ慣れないなぁ...
$\displaystyle [x^{M-N+1}] \frac{1}{(1-x)^2} \times \left ( \frac{1}{(1-x)(1+x)} \right )^{N-1}$
$\displaystyle =[x^{M-N+1}] \left ( \frac{1}{(1-x)} \right )^{N+1} \times \left ( \frac{1}{(1+x)} \right )^{N-1}$
ここまで来ると左側の $x^k$ の係数と右側の $x^{M-N+1-k}$ の係数 を組み合わせれば良い。
もっとも、★ の時点で $(1+x+x^2+\dots)^2$ の係数列が明らか (やることもほぼ同じ) なので、考察終了としてしまってもいいかもしれない。
$N=1$ がコーナーケース。
https://atcoder.jp/contests/fps-24/submissions/70854624
これはなんか組み合わせ論的解釈の方が単純に感じたなぁ
