結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
|
提出日時 | 2022-10-10 12:34:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 322 ms / 3,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 13,000 ms |
コンパイル使用メモリ | 384,452 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 07:44:47 |
合計ジャッジ時間 | 23,437 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
const MOD: usize = 998244353; fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().chars().collect::<Vec<_>>(); let mut dp = vec![vec![0usize; 27]; 27]; dp[26][26] = 1; for i in 0..n { let mut next_dp = vec![vec![0usize; 27]; 27]; if s[i] == '?' { let mut summary = vec![0usize; 27]; for pprev in 0..27 { for prev in 0..27 { if prev != 26 && pprev == prev { continue; } summary[prev] += dp[prev][pprev]; summary[prev] %= MOD; } } for cur in 0..26 { for prev in 0..27 { if cur == prev { continue; } next_dp[cur][prev] += summary[prev]; next_dp[cur][prev] += MOD - dp[prev][cur]; next_dp[cur][prev] %= MOD; } } } else { let cur = s[i] as usize - 'a' as usize; for pprev in 0..=26 { if pprev == cur { continue; } for prev in 0..=26 { if prev == cur { continue; } next_dp[cur][prev] += dp[prev][pprev]; next_dp[cur][prev] %= MOD; } } } dp = next_dp; } println!("{}", dp.iter().map(|v| v.iter().sum::<usize>()).sum::<usize>() % MOD); }