FPS24 B - 整数の組

考え方

前問からレベルアップして、無限級数が登場した。
それぞれの選び方の母関数は、以下のようになる。

• $a$ の選び方の母関数は、$A(x)=1+x$
• $b$ の選び方の母関数は、$B(x)=1+x+x^2$
• $c$ の選び方の母関数は、$C(x)=1+x^2+x^4+x^6+\dots+x^{2k}+\dots$
• $d$ の選び方の母関数は、$D(x)=1+x^3+x^6+x^9+\dots+x^{3k}+\dots$

これらの積を畳み込んで、$x^N$ の係数を答えればよい。
この畳み込みは、ある特殊な構造になっていることに気が付くと簡単に計算できる。
気づくパターンと気づかないパターンを両方解説する。

方針 $1$

$A(x)C(x)$ という組み合わせの積は、実は $1+x+x^2+x^3+\dots+x^{k}+\dots$ となる。
$B(x)D(x)$ という組み合わせの積も、実は $1+x+x^2+x^3+\dots+x^{k}+\dots$ となる。

これに気づくと、この $2$ つの畳み込み結果は明らかで、以下のようになる。
$$
A(x)B(x)C(x)D(x) = 1+2x+3x^2+4x^3+\dots+(k+1)x^k+\dots
$$

方針 $2$

分数型表現の知識を用いる。

無限級数のままでは扱いにくいので、分数型に書き換える。
$C(x)=1+x^2+x^4+x^6+\dots+x^{2k}+\dots=\dfrac{1}{1-x^2}$
$D(x)=1+x^3+x^6+x^9+\dots+x^{3k}+\dots=\dfrac{1}{1-x^3}$

すると、これら $4$ つの積は $A(x)B(x)C(x)D(x) = \dfrac{1}{(1-x)^2}$ となる。
以下の公式で $r=2$ とすることで、級数の形に戻すことができる。

$$
\begin{aligned}
\dfrac{1}{(1-x)^r}
&={}_{r-1}\mathrm{C}_{r-1}x^0+{}_{r}\mathrm{C}_{r-1}x^1+{}_{r+1}\mathrm{C}_{r-1}x^2+{}_{r+2}\mathrm{C}_{r-1}x^3+\dots\\
A(x)B(x)C(x)D(x)
&=1+2x+3x^2+4x^3+\dots+(k+1)x^k+\dots
\end{aligned}
$$

畳み込み後

いずれの方法で求めても当然同じ式になり、畳み込んだ後の $x^N$ の係数は $N+1$ である。
よって、これ（を$998244353$ で割った余り）を答えて終わり。
計算量は $O(1)$ である。

実はこの問題、形式的冪級数など用いなくても解ける。

$a+c$ の値が指定されたとしよう。
このとき、$a$ と $c$ は、$2$ で割った余りを $a$ として、残りを $c$ とする $1$ 通りの分割のみ。

$b+d$ の値が指定されたとしよう。
このとき、$b$ と $d$ は、$3$ で割った余りを $b$ として、残りを $d$ とする $1$ 通りの分割のみ。

つまり、結局 $N$ を $a+c$ と $b+d$ に分ける方法の数が答えである。
こう考えると、ややこしい計算は何もなしで $N+1$ と答えられる。

入力例1での動作

入力を受け取る。

n: 5

答えは $N+1=6$ である。
これを $998244353$ で割った余りも $6$ なので、答えは $6$。

注意点

$N+1$ は $998244353$ 以上になることがある。
最後に $998244353$ で割った余りを求めること。

別解

特になし。