結果

問題 No.567 コンプリート
コンテスト
ユーザー elphe
提出日時 2026-02-09 18:44:08
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,498 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,130 ms
コンパイル使用メモリ 199,648 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-02-09 18:44:30
合計ジャッジ時間 3,817 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin().lock()).unwrap();
    let mut stdin = stdin.split_ascii_whitespace();

    let n: usize = stdin.next().unwrap().parse().unwrap();

    use std::io::Write;
    std::io::stdout()
        .lock()
        .write_all(output(solve(n)).as_bytes())
        .unwrap();
}

const fn prepare() -> [[f64; 1 << 6]; 20] {
    let mut doubling = [[0.0; 1 << 6]; 20];

    let mut k = 0;
    while k < 6 {
        doubling[0][1 << k] = 1.0 / 6.0;
        k += 1;
    }

    let mut i = 1;
    while i < doubling.len() {
        let mut j = 0;
        while j < (1 << 6) {
            let mut k = 0;
            while k < (1 << 6) {
                doubling[i][j | k] += doubling[i - 1][j] * doubling[i - 1][k];
                k += 1;
            }
            j += 1;
        }
        i += 1;
    }

    doubling
}

fn solve(n: usize) -> f64 {
    const DOUBLING: [[f64; 1 << 6]; 20] = prepare();
    let mut dp_cur = [0.0; 1 << 6];
    let mut dp_next = [0.0; 1 << 6];
    dp_cur[0] = 1.0;

    (0..20).for_each(|i| {
        if ((n >> i) & 1) == 1 {
            dp_next.fill(0.0);
            (0..(1 << 6)).for_each(|j| {
                (0..(1 << 6)).for_each(|k| dp_next[j | k] += dp_cur[j] * DOUBLING[i][k])
            })
        } else {
            dp_next.copy_from_slice(&dp_cur);
        }
        dp_cur.swap_with_slice(&mut dp_next);
    });
    dp_cur[(1 << 6) - 1]
}

fn output(ans: f64) -> String {
    ans.to_string() + "\n"
}
0