AtCoder Beginner Contest 333 F

https://atcoder.jp/contests/abc333/tasks/abc333_f

N個の中でiが最後まで残る確率を $p_i^N$ と書くと、

$p_1^1 = 1$

1回動かすと、

$\displaystyle \begin{pmatrix} p_1^n \\ p_2^n \\ \vdots \\ p_n^n \end{pmatrix} =\frac{1}{2} \begin{pmatrix} 0 \\ p_1^{n-1} \\ \vdots \\ p_{n-1}^{n-1} \end{pmatrix} + \frac{1}{2} \begin{pmatrix} p_n^n \\ p_1^n \\ \vdots \\ p_{n-1}^n \end{pmatrix}$

なので、最初の式の $p_n^n$ に最後の式を代入して、という処理を次々していけば、

$\displaystyle p_1^n = \sum_{k=1}^{n-1}\frac{1}{2^{n+1-k}}{p_k^{n-1}} + \frac{1}{2^n}p_1^n$

となるので、 $p_1^n$ が求まって、他の確率も求まります。

// Takahashi Quest
#![allow(non_snake_case)]

const D: i64 = 998244353;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse(a: i64, d: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, d).unwrap();
    if x >= 0 {
        x % d
    }
    else {
        x % d + d
    }
}


//////////////////// process ////////////////////

fn normalize(p: i64) -> i64 {
    let q = p % D;
    if q < 0 { q + D } else { q }
}

fn update(ps: Vec<i64>, n: usize) -> Vec<i64> {
    let mut new_ps: Vec<i64> = vec![0; n];
    let half = inverse(2, D);
    let mut s: i64 = 0;
    let mut c = half;
    for k in (0..n-1).rev() {
        c = c * half % D;
        s = (s + c * ps[k]) % D
    }
    new_ps[0] = normalize(s * inverse(1 - c + D, D));
    for k in 1..n {
        new_ps[k] = normalize((ps[k-1] + new_ps[k-1]) * half)
    }
    new_ps
}

fn F(N: usize) {
    let mut ps: Vec<i64> = vec![1];
    for n in 2..N+1 {
        ps = update(ps, n)
    }
    println!("{}", ps.iter().map(|&p| p.to_string()).
                            collect::<Vec<_>>().join(" "))
}

fn main() {
    let N = read();
    F(N)
}