結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
![]() |
提出日時 | 2023-03-11 15:00:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,063 ms / 3,000 ms |
コード長 | 2,343 bytes |
コンパイル時間 | 4,070 ms |
コンパイル使用メモリ | 254,896 KB |
最終ジャッジ日時 | 2025-02-11 10:00:41 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=int; using ld=long double; ld pie=3.141592653589793; ll inf=69; ll mod=998244353; int main(){ ll n; cin >> n; string s; cin >> s; for (ll i = 1; i < s.size(); i++) { if (s[i]!='?'&&s[i]==s[i-1]) { cout << 0 << endl; return 0; } if (i>=2) { if (s[i]!='?'&&s[i]==s[i-2]) { cout << 0 << endl; return 0; } } } ll ans=0; vector<vector<vector<ll>>>dp(n,vector<vector<ll>>(26,vector<ll>(26,0))); if (s[0]=='?') { for (ll i = 0; i < 26; i++) { dp[0][i][i]=1; } }else{ dp[0][s[0]-'a'][s[0]-'a']=1; } for (ll i = 1; i < s.size(); i++) { if (s[i]!='?') { for (ll j = 0; j < 26; j++) { if (j==s[i]-'a') { continue; } for (ll k = 0; k < 26; k++) { if (k==s[i]-'a') { continue; } dp[i][s[i]-'a'][j]+=dp[i-1][j][k]; if (dp[i][s[i]-'a'][j]>mod) { dp[i][s[i]-'a'][j]-=mod; } } } }else{ for (ll l = 0; l < 26; l++) { for (ll j = 0; j < 26; j++) { if (j==l) { continue; } for (ll k = 0; k < 26; k++) { if (k==l) { continue; } dp[i][l][j]+=dp[i-1][j][k]; if (dp[i][l][j]>mod) { dp[i][l][j]-=mod; } } } } } } for (ll i = 0; i < 26; i++) { for (ll j = 0; j < 26; j++) { ans+=dp[n-1][i][j]; ans%=mod; } } cout << ans << endl; }