「FPS 24 題」全部解く: H「ジャンプ」

解きます

解く

行動パターンは以下のようになります.

• 以下を$N$回繰り返す
  • 0回以上$a=0$で$b\ge1$な選択をする
  • $a=1$で$b\ge0$な選択を1回する
• 0回以上$a=0$で$b\ge1$な選択をする

「0回以上$a=0$で$b\ge1$な選択をする」に対応する関数は
$$\begin{align}
\prod_{k=0}^\infty\left(\frac x{1-x}\right)^k
&= \frac 1{1-\frac x{1-x}} \\
&= \frac{1-x}{1-2x} \\
\end{align}$$
です. ($k$次の係数が$y$座標を$k$増やす操作の数に対応します) そして, $N$回反復した中身は
$$\frac 1{1-x}\frac{1-x}{1-2x}=\frac1{1-2x}$$
です.

つまり, 求めたいものは
$$\left[x^M\right]\frac1{\left(1-2x\right)^N}\frac{1-x}{1-2x}=\left[x^M\right]\frac{1-x}{\left(1-2x\right)^{N+1}}$$
です. ここまで来ればもうあとは弄るだけです.
$$\begin{align}
\left[x^M\right]\frac{1-x}{\left(1-2x\right)^{N+1}}
&= \left[x^M\right]\frac1{\left(1-2x\right)^{N+1}} - \left[x^{M-1}\right]\frac1{\left(1-2x\right)^{N+1}} \\
&= 2^M\binom{N+M}{N} - 2^{M-1}\binom{N+M-1}{N} \\
\end{align}$$

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

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize,
        m: usize,
    }
    // 階乗テーブル
    let factorial = {
        let mut r = vec![Mint::raw(1)];
        for i in 1..=400000 {
            r.push(r[i - 1] * i);
        }
        r
    };
    // 二項係数
    let binom = |a: usize, b: usize| factorial[a] / (factorial[b] * factorial[a - b]);
    println!(
        "{}",
        Mint::raw(2).pow(m as u64 - 1) * (binom(n + m, n) * 2 - binom(n + m - 1, n))
    );
}

提出(3 ms):

終わり

トップページによると, この問題までが初心者向けらしいです. 明日から怖い
以上です