結果

問題 No.3040 Aoiスコア
ユーザー Blue_S
提出日時 2025-01-07 21:47:27
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 1,769 bytes
コンパイル時間 12,524 ms
コンパイル使用メモリ 399,488 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 20:54:53
合計ジャッジ時間 13,605 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

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

const MOD: usize = 998_244_353;

fn main() {
    input! {
        n: usize,
        m: usize,
        s: Bytes,
        ab: [(Usize1, Usize1); m],
    }

    let mut pow_26 = vec![1];
    for _ in 0..=6000 {
        pow_26.push((pow_26.last().unwrap() * 26) % MOD);
    }

    let mut e = vec![vec![]; n];
    for &(a, b) in &ab {
        e[a].push(b);
        e[b].push(a);
    }

    let hatena = s.iter().filter(|c| **c == b'?').count();

    let ans = s
        .iter()
        .copied()
        .zip(e.iter())
        .filter(|x| x.0 == b'o' || x.0 == b'?')
        .map(|(c, e)| {
            let a = e.iter().filter(|e| s[**e] == b'a').count();
            let i = e.iter().filter(|e| s[**e] == b'i').count();
            let w = e.iter().filter(|e| s[**e] == b'?').count();
            if c == b'o' {
                (a * i) * pow_26[hatena]
                    + if hatena > 0 {
                        (a * w + w * i) * pow_26[hatena - 1]
                    } else {
                        0
                    }
                    + if hatena > 1 {
                        w * (w - 1) * pow_26[hatena - 2]
                    } else {
                        0
                    }
            } else {
                (a * i) * pow_26[hatena - 1]
                    + if hatena > 1 {
                        (a * w + w * i) * pow_26[hatena - 2]
                    } else {
                        0
                    }
                    + if hatena > 2 {
                        w * (w - 1) * pow_26[hatena - 3]
                    } else {
                        0
                    }
            }
        })
        .fold(0, |acc, a| (acc + a) % MOD);

    println!("{}", ans);
}
0