結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
![]() |
提出日時 | 2023-08-01 17:14:38 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 363 ms / 3,000 ms |
コード長 | 1,653 bytes |
コンパイル時間 | 3,262 ms |
コンパイル使用メモリ | 140,776 KB |
実行使用メモリ | 267,648 KB |
最終ジャッジ日時 | 2024-10-11 08:33:17 |
合計ジャッジ時間 | 15,236 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <limits.h> #include <map> #include <queue> #include <set> #include <string.h> #include <vector> using namespace std; typedef long long ll; const ll MOD = 998244353; ll dp[50010][26][26]; int main() { int N; cin >> N; string S; cin >> S; if (N == 1) { if (S[0] == '?') { cout << 26 << endl; } else { cout << 1 << endl; } return 0; } memset(dp, 0, sizeof(dp)); for (int u = 0; u < 26; ++u) { if (S[0] != '?' && S[0] - 'a' != u) continue; for (int v = 0; v < 26; ++v) { if (u == v) continue; if (S[1] != '?' && S[1] - 'a' != v) continue; dp[1][u][v]++; } } for (int i = 2; i < N; ++i) { char s = S[i]; ll sum[26]; memset(sum, 0, sizeof(sum)); for (int u = 0; u < 26; ++u) { for (int v = 0; v < 26; ++v) { sum[v] += dp[i - 1][u][v]; sum[v] %= MOD; } } if (s == '?') { for (int u = 0; u < 26; ++u) { for (int v = 0; v < 26; ++v) { if (u == v) continue; dp[i][u][v] += (sum[u] - dp[i - 1][v][u] + MOD) % MOD; dp[i][u][v] %= MOD; } } } else { int v = s - 'a'; for (int u = 0; u < 26; ++u) { if (u == v) continue; dp[i][u][v] += (sum[u] - dp[i - 1][v][u] + MOD) % MOD; dp[i][u][v] %= MOD; } } } ll ans = 0; for (int u = 0; u < 26; ++u) { for (int v = 0; v < 26; ++v) { if (u == v) continue; ans += dp[N - 1][u][v]; ans %= MOD; } } cout << ans << endl; return 0; }