FPS24 F - 色紙

考え方

方針が $2$ つある。
どちらの考え方も母関数らしい考え方で手計算で最後の答えが出るので、両方紹介する。

方針 $1$

赤く塗らない紙を選ぶ方法を考える。

まず偶奇を考えずに選ぶ。
すると、$1$ 枚ごとに選ぶか選ばないかの選択があるので、母関数は $(1+x)^N$ となる。

実際には青色が偶数枚で黄色が奇数枚、つまり赤く塗らない紙は奇数枚でなければならない。
そこで、この $(1+x)^N$ の奇数次だけ残して偶数次を削除する。
$f(x)$ の奇数次だけ取り出したものは $\dfrac{f(x)-f(-x)}{2}$ である。
つまり、赤く塗らない紙を奇数枚選ぶ母関数は $\dfrac{(1+x)^N-(1-x)^N}{2}$ となる。

さて、赤く塗らない紙を青色偶数枚と黄色奇数枚で塗り分ける方法を考える。
併せて $k$ 枚ある場合、偶奇を考えずに塗る方法は $2^k$ 通りある。
青色と黄色の総入れ替えを考えると、青色偶数枚と黄色奇数枚になっているのはそのちょうど半分。

つまり、$\dfrac{(1+x)^N-(1-x)^N}{2}$ の $x^k$ の係数に $2^{k-1}$ をかけて合計すれば答え。
そしてこれは、形式的に $x=2$ を代入して $2$ で割ればよい。
よって、答えは $\dfrac{3^N-(-1)^N}{2^2}$。

計算量は、繰り返し二乗法 $3$ 回分で $O(\log N)$。

方針 $2$

E問題と同じく、各色の枚数を選んだあとで並べ替えを行うので、指数型母関数の出番。
各色の塗り方の母関数は以下のようになる。

• $R(x) = 1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+\dfrac{x^4}{24}+\dots = e^x$
• $B(x) = 1+\dfrac{x^2}{2}+\dfrac{x^4}{24}+\dfrac{x^6}{720}+\dots = \cosh x$
• $Y(x) = x+\dfrac{x^3}{6}+\dfrac{x^5}{120}+\dfrac{x^7}{5040}+\dots = \sinh x$

よって、これらを掛け合わせて $\dfrac{x^N}{N!}$ の係数を答えればよい。
実際にかけ合わせると、以下のようになる。
$$
\begin{aligned}
R(x)B(x)Y(x)
&= e^x\cosh x\sinh x \\
&= \dfrac{e^x\sinh 2x}{2} \\
&= \dfrac{e^x(e^{2x}-e^{-2x})}{2^2} \\
&= \dfrac{e^{3x}-e^{-x}}{2^2}.
\end{aligned}
$$

$\dfrac{x^N}{N!}$ の係数は $\dfrac{3^N-(-1)^N}{2^2}$ なので、これが答え。

計算量は、繰り返し二乗法 $3$ 回分で $O(\log N)$。

入力例1での動作

入力を受け取る。

n: 3

求める値は次の通り。
$$
\dfrac{3^3-(-1)^3}{2^2}
=\dfrac{27+1}{4}
=7
$$

よって、答えは $7$ となる。

注意点

$998244353$ で割った余りを求めるため、$2^2$ での除算には逆元を用いる。
逆元は繰り返し二乗法で求める。

別解

特になし。