結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
![]() |
提出日時 | 2021-08-19 23:01:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,660 bytes |
コンパイル時間 | 3,743 ms |
コンパイル使用メモリ | 233,644 KB |
実行使用メモリ | 325,504 KB |
最終ジャッジ日時 | 2024-11-08 16:27:00 |
合計ジャッジ時間 | 43,794 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 10 TLE * 15 -- * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 2000000 #define MOD 998244353 #define INF 1000000000 int main(){ int N; string S; cin>>N>>S; if(N==1){ if(S[0]=='?'){ cout<<26<<'\n'; }else{ cout<<1<<'\n'; } return 0; } vector<vector<vector<ll>>> dp(N,vector<vector<ll>>(26,vector<ll>(26,0))); if(S[0]=='?'&&S[1]=='?'){ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k){ continue; } dp[1][j][k]=1; } } }else if(S[0]=='?'){ for(int j=0;j<26;j++){ if(j==S[1]-'a'){ continue; } dp[1][j][S[1]-'a']=1; } }else if(S[1]=='?'){ for(int k=0;k<26;k++){ if(S[0]-'a'==k){ continue; } dp[1][S[0]-'a'][k]=1; } }else{ if(S[0]!=S[1]){ dp[1][S[0]-'a'][S[1]-'a']=1; } } for(int i=2;i<N;i++){ if(S[i]!='?'){ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k||S[i]-'a'==j||S[i]-'a'==k){ continue; } dp[i][k][S[i]-'a']+=dp[i-1][j][k]; dp[i][k][S[i]-'a']%=MOD; } } }else{ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ for(int l=0;l<26;l++){ if(j==k||k==l||l==j){ continue; } dp[i][k][l]+=dp[i-1][j][k]; dp[i][k][l]%=MOD; } } } } } ll ans=0; for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ ans+=dp[N-1][j][k]; ans%=MOD; } } cout<<ans<<'\n'; }