結果
問題 |
No.1741 Arrays and XOR Procedure
|
ユーザー |
|
提出日時 | 2022-09-30 09:59:41 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 914 bytes |
コンパイル時間 | 14,712 ms |
コンパイル使用メモリ | 378,488 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-12-22 18:39:44 |
合計ジャッジ時間 | 16,570 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
const MOD: usize = 998244353; fn is_odd(n: usize, k: usize) -> bool { (n & k) == k } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut b = String::new(); std::io::stdin().read_line(&mut b).ok(); let b: Vec<isize> = b.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let mut dp = vec![0usize; n+1]; let mut total = 1usize; for i in 0..n { let odd = is_odd(n-1, i); if b[i] == -1 { if odd { dp[i+1] = total; } else { dp[i+1] = 2*dp[i] % MOD; } total *= 2; total %= MOD; } else if b[i] == 1 && odd { dp[i+1] = MOD + total - dp[i]; dp[i+1] %= MOD; } else { dp[i+1] = dp[i]; } } println!("{}", dp[n]); }