「FPS 24 題」全部解く: F「色紙」

解きます

解く

昨日と同じ方針(指数型母関数)で立式します.
各色に対応するのが

• 赤: $\sum_{k=0}^\infty\frac{x^k}{k!} = e^x$
• 青: $\sum_{k=0}^\infty\frac{x^{2k}}{\left(2k\right)!} = \cosh x$
• 黄: $\sum_{k=0}^\infty\frac{x^{2k+1}}{\left(2k+1\right)!} = \sinh x$

なのでこれら3つと$N!$を掛けて$N$次の項の係数が答えになります.
$$\begin{align}
&N!\left[x^N\right]\left(\sum_{k=0}^\infty\frac{x^k}{k!}\right)\left(\sum_{k=0}^\infty\frac{x^{2k}}{\left(2k\right)!}\right)\left(\sum_{k=0}^\infty\frac{x^{2k+1}}{\left(2k+1\right)!}\right) \\
&\qquad= N!\left[x^N\right]\left(e^x \cosh x \sinh x\right) \\
&\qquad= N!\left[x^N\right]\frac{e^x\left(e^{2x}-e^{-2x}\right)}4 \\
&\qquad= N!\left[x^N\right]\frac{e^{3x}-e^{-x}}4 \\
&\qquad= N!\frac{\frac{3^N}{N!}-\frac{\left(-1\right)^N}{N!}}4 \\
&\qquad= \frac{3^N-\left(-1\right)^N}4 \\
\end{align}$$
このように求まりました.

use ac_library::*;
use proconio::*;

type Mint = ModInt998244353;

fn main() {
    input! { n: u64 }
    println!("{}", (Mint::raw(3).pow(n) - (-Mint::raw(1)).pow(n)) / 4);
}

提出(1 ms):

終わり

整数問題で唐突に指数関数とか持ってきたら答え出るって黒魔術見てるみたいでおもしろいですね
以上です