指数型母関数の練習問題です。(指数型母関数については ABC422-G の解説 などを参考にしてください。)

赤い紙は何枚でもよいので、対応する母関数 \(R(x)\) は

\[R(x) = \sum_{n=0}^\infty \frac{x^n}{n!} = e^x\]

となります。同様に青い紙と黄色い紙について考えると、青い紙は偶数枚、黄色い紙は奇数枚である必要があるので対応する母関数 \(B(x), Y(x)\) は

\[B(x) = \sum_{n \geq 0, n:偶数} \frac{x^n}{n!}\]

\[Y(x) = \sum_{n \geq 0, n:奇数} \frac{x^n}{n!}\]

となりますが、ここで形式的冪級数 \(A(x)=\sum_{n=0}^\infty a_n x^n\) について

\[\frac{A(x) + A(-x)}{2} = \sum_{n \geq 0, n:偶数} a_n x^n\]

\[\frac{A(x) - A(-x)}{2} = \sum_{n \geq 0, n:奇数} a_n x^n\]

が成り立つことを考えると、

\[B(x) = \sum_{n \geq 0, n:偶数} \frac{x^n}{n!} = \frac{e^x + e^{-x}}{2}\]

\[Y(x) = \sum_{n \geq 0, n:奇数} \frac{x^n}{n!} = \frac{e^x - e^{-x}}{2}\]

を得ます。よって答えは

\[ \begin{aligned} &\left[\frac{x^N}{N!}\right] R(x) B(x) Y(x) \\ &= \left[\frac{x^N}{N!}\right] e^x\frac{e^x + e^{-x}}{2}\times \frac{e^x - e^{-x}}{2} \\ &= \left[\frac{x^N}{N!}\right] \frac{e^{3x} - e^{-x}}{4} \end{aligned} \]

です。

\[\left[\frac{x^N}{N!}\right] e^{ax} = a^n\]

なので、最終的に計算すべき値は

\[\frac{3^N - (-1)^N}{4}\]

となり、これは \(\mathrm{O}(\log N)\) で計算できます。