結果

問題 No.3044 よくあるカエルさん
コンテスト
ユーザー Blue_S
提出日時 2025-01-16 05:48:59
言語 Rust
(1.83.0 + proconio)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,621 bytes
コンパイル時間 13,647 ms
コンパイル使用メモリ 400,128 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-18 00:35:07
合計ジャッジ時間 15,622 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

 use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: Usize1,
        t: usize,
        k: f64,
        l: f64,
    }

    let mut dp = vec![1.];
    for i in 1..t {
        let mut next = 0.;
        if i >= 1 {
            next += (k - 1.) / 6. * dp[i - 1];
        }
        if i >= 2 {
            next += (l - k) / 6. * dp[i - 2];
        }
        if i >= t {
            next += (7. - k) / 6. * dp[i - t];
        }
        dp.push(next);
    }
    assert_eq!(dp.len(), t);

    if n <= t {
        println!("{}", dp[n]);
    }
    let mut x = vec![vec![0.; t]; t];

    x[0][0] = (k - 1.) / 6.;
    x[0][1] = (l - k) / 6.;
    x[0][t - 1] = (7. - k) / 6.;
    for i in 1..t {
        x[i][i - 1] = 1.;
    }

    let coef = pow(&x, n);

    let ans = coef
        .last()
        .unwrap()
        .iter()
        .zip(dp.iter().rev())
        .map(|(coef, dp)| coef * dp)
        .fold(0., |acc, a| acc + a);
    println!("{}", ans);
}

fn multiple(a: &Vec<Vec<f64>>, b: &Vec<Vec<f64>>) -> Vec<Vec<f64>> {
    let n = a.len();
    let mut res = vec![vec![0.; n]; n];
    for i in 0..n {
        for j in 0..n {
            res[i][j] = (0..n).map(|k| a[i][k] * b[k][j]).fold(0., |acc, a| acc + a);
        }
    }
    res
}

fn pow(a: &Vec<Vec<f64>>, mut n: usize) -> Vec<Vec<f64>> {
    let m = a.len();
    let mut res = vec![vec![0.; m]; m];
    for i in 0..m {
        res[i][i] = 1.;
    }
    let mut base = a.clone();
    while n > 0 {
        if n & 1 == 1 {
            res = multiple(&res, &base);
        }
        base = multiple(&base, &base);
        n >>= 1;
    }
    res
}
0