「FPS 24 題」全部解く: B「整数の組」

解きます

解く

4つの整数に対応する関数はそれぞれ

• $a$: $1+x$
• $b$: $1+x+x^2$
• $c$: $\frac{1}{1-x^2}$
• $d$: $\frac{1}{1-x^3}$

です. なので, 求めるものは
$$\left[x^N\right]\left(1+x\right)\left(1+x+x^2\right)\frac{1}{1-x^2}\frac{1}{1-x^3}$$
なんですが,
$$\begin{align}
&\left(1+x\right)\left(1+x+x^2\right)\frac1{1-x^2}\frac1{1-x^3}\\
&= \left(1+x\right)\left(1+x+x^2\right)\frac1{\left(1+x\right)\left(1-x\right)}\frac1{\left(1+x+x^2\right)\left(1-x\right)}\\
&= \frac1{\left(1-x\right)^2}
\end{align}$$
と変形できるため, 結局
$$\left[x^N\right]\frac{1}{\left(1-x\right)^2}$$
になります. これは$1+2x+3x^2+4x^3+\dots=\sum_{k=0}^\infty \left(k+1\right)x^k$であることで有名なので, 答えが$N+1$と分かりました.

use proconio::*;

fn main() {
    input! { n: u32 }
    println!("{}", (n + 1) % 998244353);
}

提出(1 ms):

終わり

昨日に比べて随分簡単ですね (と書こうとしたらmodとり忘れて1WA出したんですが)
以上です