FPS24 D - 数列 2

考え方

$A$ は順番自由となっているが、条件より同じ数は含まれないので、$B$ のパターン数の $N!$ 倍である。
よって、このような $B$ のパターンを数えればよい。
$B$ は、階差数列の値が全て正の奇数で、初項が $0$ 以上、末項が $M$ 以下という条件である。

とりあえず、階差数列の選び方を考えてみる。
正の奇数の選び方の母関数は、以下。
$$
P(x) = x+x^3+x^5+\dots+x^{2k+1}+\dots = \dfrac{x}{1-x^2}
$$

これを $N-1$ 回選ぶので、母関数を $N-1$ 乗する。
$$
\{P(x)\}^{N-1} = \dfrac{x^{N-1}}{(1-x^2)^{N-1}}
$$

これの $x^k\ (k<=M)$ の係数が、初項と末項の差が $k$ であるような階差数列の選び方の数。
その階差数列ごとに、初項を $M-k+1$ 通りから選ぶことができる。
よって、$x^k$ の係数に $M-k+1$ を掛けた値を、$0 \leq k\leq M$ 範囲で総和を取ればよい。

この時点でも実装に移ることは可能。（A問題やC問題と同様なので、解答例は省略）
だが、せっかくなのでもう少し考察してみる。

$x^k$ の係数に $M-k+1$ を掛けた値を、$0 \leq k\leq M$ 範囲で総和を取る、という計算も畳み込みにできる。
つまり、以下の $Q(x)$ とも畳み込んで、$x^M$ の係数を見ればよい。
$\{P(x)\}^{N-1}$ の $x^k$ の項に $Q(x)$ の $x^{M-k}$ の係数である $M-k+1$ が掛けられる。
$$
Q(x)=1+2x+3x^2+\dots +(k+1)x^{k}+\dots = \dfrac{1}{(1-x)^2}
$$

ということで、全体として、以下の $x^M$ の項を見ることになる。
$$
\{P(x)\}^{N-1}Q(x) = \dfrac{x^{N-1}}{(1-x^2)^{N-1}(1-x)^2} = \dfrac{x^{N-1}(1+x)^2}{(1-x^2)^{N+1}}
$$

分子は $3$ 項しかないので、$B$ のパターン数は以下でよい。

• $M<N-1$ である場合、$0$
• $M \geq N-1$ で $M$ と $N$ の偶奇が同じ場合、$2{}_{\frac{M+N}{2}}\mathrm{C}_{N}$
• $M \geq N-1$ で $M$ と $N$ の偶奇が異なる場合、${}_{\frac{M+N-1}{2}}\mathrm{C}_{N}+{}_{\frac{M+N+1}{2}}\mathrm{C}_{N}$

そして、これに $N!$ を掛ければ答えである。

入力例1での動作

入力を受け取る。

n: 2
m: 3

$M<N-1$ ではなく、$M-N=1$ は奇数なので、$M$ と $N$ の偶奇が異なる場合に入る。
ソート済みの $B$ のパターン数は、${}_2\mathrm{C}_2+{}_3\mathrm{C}_2=1+3=4$ となる。

これを $N!=2$ 倍して、元の数列 $A$ のパターン数に戻す。
よって、答えは $4\times 2=8$ となる。

注意点

二項係数は $998244353$ で割った余りを求めながら計算する。
階乗を用いて二項係数を求める際の除算には逆元を用い、逆元は繰り返し二乗法で求める。

別解

特になし。