結果
問題 | No.2131 Concon Substrings (COuNt Version) |
ユーザー | phspls |
提出日時 | 2022-11-26 14:26:07 |
言語 | Rust (1.72.1) |
結果 |
AC
|
実行時間 | 1,271 ms / 2,000 ms |
コード長 | 1,034 bytes |
コンパイル時間 | 910 ms |
コンパイル使用メモリ | 153,372 KB |
実行使用メモリ | 166,140 KB |
最終ジャッジ日時 | 2023-07-26 01:01:24 |
合計ジャッジ時間 | 9,982 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 572 ms
76,608 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 1,271 ms
166,108 KB |
testcase_08 | AC | 314 ms
43,200 KB |
testcase_09 | AC | 1,268 ms
166,140 KB |
testcase_10 | AC | 1,270 ms
165,340 KB |
testcase_11 | AC | 885 ms
115,920 KB |
testcase_12 | AC | 839 ms
110,176 KB |
testcase_13 | AC | 2 ms
4,376 KB |
testcase_14 | AC | 369 ms
50,084 KB |
testcase_15 | AC | 298 ms
40,820 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 264 ms
36,620 KB |
testcase_18 | AC | 270 ms
37,088 KB |
testcase_19 | AC | 136 ms
19,704 KB |
ソースコード
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 maxcnt = n/3; let mut dp = vec![vec![vec![0usize; 3]; maxcnt+1]; n+1]; dp[0][0][0] = 1; for i in 0..n { for j in 0..=maxcnt { for pat in 0..3 { if dp[i][j][pat] == 0 { continue; } for c in 0..26 { let npat = pat + if (pat == 0 && c == 2) || (pat == 1 && c == 14) || (pat == 2 && c == 13) { 1 } else { 0 }; if npat < 3 { dp[i+1][j][npat] += dp[i][j][pat]; dp[i+1][j][npat] %= MOD; } else { dp[i+1][j+1][0] += dp[i][j][pat]; dp[i+1][j+1][0] %= MOD; } } } } } println!("{}", dp[n].iter().enumerate().map(|(i, v)| v.iter().sum::<usize>() % MOD * i % MOD).sum::<usize>() % MOD); }