結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
![]() |
提出日時 | 2023-08-01 16:43:16 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,917 bytes |
コンパイル時間 | 3,057 ms |
コンパイル使用メモリ | 141,948 KB |
実行使用メモリ | 267,776 KB |
最終ジャッジ日時 | 2024-10-11 08:05:41 |
合計ジャッジ時間 | 17,206 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 WA * 2 |
ソースコード
#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)); if (S[0] == '?') { for (int u = 0; u < 26; ++u) { if (S[1] == '?') { for (int v = 0; v < 26; ++v) { if (u == v) continue; dp[1][u][v]++; } } else { int v = S[1] - 'a'; dp[1][u][v]++; } } } else { int u = S[0] - 'a'; if (S[1] == '?') { for (int v = 0; v < 26; ++v) { if (u == v) continue; dp[1][u][v]++; } } else { int v = S[1] - 'a'; 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; }