AtCoder Beginner Contest 382 E

https://atcoder.jp/contests/abc382/tasks/abc382_e

一つのパックにレアカードがi枚入っている確率は、

で得られます。

n枚以上手に入れるまでのパック数の期待値をとしたとき、まずです。一つパックを開けたことを考えます。入力例2でを考えると、1枚か2枚だったとき1回で終わりです。0枚だったとき、1回に加えてさらに回かかります。これを式にすると、

で、ここからが求められます。やも順に求められます。

// Expansion Packs
#![allow(non_snake_case)]


//////////////////// 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()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


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

fn read_input() -> (usize, Vec<i32>) {
    let v: Vec<usize> = read_vec();
    let X = v[1];
    let P: Vec<i32> = read_vec();
    (X, P)
}

fn mul(f: Vec<f64>, g: Vec<f64>) -> Vec<f64> {
    let mut h: Vec<f64> = vec![0.0; f.len() + g.len() - 1];
    for i in 0..f.len() {
        for j in 0..g.len() {
            h[i+j] += f[i] * g[j]
        }
    }
    h
}

fn calc_probs(P: Vec<i32>) -> Vec<f64> {
    let N = P.len();
    let mut probs: Vec<f64> = vec![1.0];
    for i in 0..N {
        let p = (P[i] as f64) / 100.0;
        probs = mul(probs, vec![1.0 - p, p])
    }
    probs
}

fn F(X: usize, P: Vec<i32>) -> f64 {
    let N = P.len();
    let probs = calc_probs(P);
    
    let mut E: Vec<f64> = vec![1.0; X+1];
    for n in 1..X+1 {
        if n <= N {
            let mut s: f64 = 0.0;
            for j in 1..n {
                s += probs[n-j] * E[j]
            }
            E[n] = (s + 1.0) / (1.0 - probs[0])
        }
        else {
            let s: f64 = (n-N..n).map(|j| probs[n-j] * E[j]).sum::<f64>();
            E[n] = (s + 1.0) / (1.0 - probs[0])
        }
    }
    E[X]
}

fn main() {
    let (X, P) = read_input();
    println!("{}", F(X, P))
}