結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー ntk-ta01
提出日時 2021-07-05 14:55:04
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 3,233 bytes
コンパイル時間 21,706 ms
コンパイル使用メモリ 392,120 KB
実行使用メモリ 23,808 KB
最終ジャッジ日時 2024-07-01 11:57:19
合計ジャッジ時間 20,333 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;
fn main() {
    input! {
        mut a: String,
        mut b: String,
    }
    const MOD: i32 = 1_000_000_007;
    let mut ds = vec![];
    for c in b.chars() {
        let n = c as i32 - 48;
        ds.push(n);
    }
    let mut dp1 = vec![vec![vec![vec![vec![0; 8]; 3]; 2]; 2]; ds.len() + 1];
    // dp1[i][is_less][has_3][mod3][mod8]
    dp1[0][0][0][0][0] = 1;
    for i in 0..ds.len() {
        for j in 0..=1 {
            for k in 0..=1 {
                for m in 0..3 {
                    for n in 0..8 {
                        let lim = if j == 1 { 9 } else { ds[i] };
                        for d in 0..=lim {
                            let is_less: usize = if j == 1 || d < lim { 1 } else { 0 };
                            let has_3: usize = if k == 1 || d == 3 { 1 } else { 0 };
                            let mod_3: usize = (m + d as usize) % 3;
                            let mod_8: usize = (n * 10 + d as usize) % 8;
                            dp1[i + 1][is_less][has_3][mod_3][mod_8] += dp1[i][j][k][m][n];
                            dp1[i + 1][is_less][has_3][mod_3][mod_8] %= MOD;
                        }
                    }
                }
            }
        }
    }
    let mut answer = 0;
    for d in dp1[ds.len()].iter() {
        for k in 0..=1 {
            for m in 0..=2 {
                for n in 0..8 {
                    if (k == 1 || m == 0) && n != 0 {
                        answer += d[k][m][n];
                        answer %= MOD;
                    }
                }
            }
        }
    }
    let mut ds = vec![];
    for c in a.chars() {
        let n = c as i32 - 48;
        ds.push(n);
    }
    for d in ds.iter_mut().rev() {
        if *d == 0 {
            *d = 9;
        } else {
            *d -= 1;
            break;
        }
    }
    if ds[0] == 0 {
        ds.remove(0);
    }
    let mut dp2 = vec![vec![vec![vec![vec![0; 8]; 3]; 2]; 2]; ds.len() + 1];
    // dp2[i][is_less][has_3][mod3][mod8]
    dp2[0][0][0][0][0] = 1;
    for i in 0..ds.len() {
        for j in 0..=1 {
            for k in 0..=1 {
                for m in 0..3 {
                    for n in 0..8 {
                        let lim = if j == 1 { 9 } else { ds[i] };
                        for d in 0..=lim {
                            let is_less: usize = if j == 1 || d < lim { 1 } else { 0 };
                            let has_3: usize = if k == 1 || d == 3 { 1 } else { 0 };
                            let mod_3: usize = (m + d as usize) % 3;
                            let mod_8: usize = (n * 10 + d as usize) % 8;
                            dp2[i + 1][is_less][has_3][mod_3][mod_8] += dp2[i][j][k][m][n];
                            dp2[i + 1][is_less][has_3][mod_3][mod_8] %= MOD;
                        }
                    }
                }
            }
        }
    }
    for d in dp2[ds.len()].iter() {
        for k in 0..=1 {
            for m in 0..=2 {
                for n in 0..8 {
                    if (k == 1 || m == 0) && n != 0 {
                        answer -= d[k][m][n];
                        answer %= MOD;
                    }
                }
            }
        }
    }
    println!("{}", answer);
}
0