結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
|
提出日時 | 2023-07-22 18:29:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 632 ms / 3,000 ms |
コード長 | 2,151 bytes |
コンパイル時間 | 1,177 ms |
コンパイル使用メモリ | 107,168 KB |
最終ジャッジ日時 | 2025-02-15 18:08:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
/* O(N*σ^3)でTLE */ #include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<stack> #include<numeric> #include<queue> #include<cmath> #include<deque> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<int,int> P; typedef pair<ll,P> PP; const ll MOD=998244353; int main(){ int N; cin>>N; string S; cin>>S; if(N==1){ cout<<(S[0]=='?'?26:1)<<endl; return 0; } vector dp(N+1,vector<vector<ll>>(26,vector<ll>(26,0))); vector<ll> sum(26,0); for(int j=0;j<26;j++){ if( S[0]-'a' == j || S[0]=='?' ){ for(int k=0;k<26;k++){ if(j==k) continue; if(S[1]-'a'==k || S[1]=='?'){ dp[1][j][k]=1; sum[k]+=1; sum[k]%=MOD; } } } } for(int i=2;i<N;i++){ for(int k=0;k<26;k++){ /* dp[i][j][k]=i文字目がk, i-1文字目がj */ if(S[i]!='?'){ if(S[i]-'a'!=k){ //i=2のとき, i=0文字目がS[i]-'a'だった時を引けば良い dp[i][k][S[i]-'a']+=(sum[k]-dp[i-1][S[i]-'a'][k]+MOD)%MOD; dp[i][k][S[i]-'a']%=MOD; } }else{ for(int l=0;l<26;l++){ //直前の文字列は順番に, j,k,l となっている. i文字目がl文字目 if(k!=l){ dp[i][k][l]+=(sum[k]-dp[i-1][l][k]+MOD)%MOD; dp[i][k][l]%=MOD; } } } } for(int k=0;k<26;k++){ sum[k]=0; for(int j=0;j<26;j++){ sum[k]+=dp[i][j][k]; sum[k]%=MOD; } } } ll ans=0; for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k) continue; ans+=dp[N-1][j][k]; ans%=MOD; } } cout<<ans<<endl; }