結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
|
提出日時 | 2021-08-13 21:54:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,573 ms / 3,000 ms |
コード長 | 1,445 bytes |
コンパイル時間 | 2,120 ms |
コンパイル使用メモリ | 174,860 KB |
実行使用メモリ | 320,256 KB |
最終ジャッジ日時 | 2024-11-08 15:14:06 |
合計ジャッジ時間 | 61,427 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
//#include <atcoder/all> #include <bits/stdc++.h> #include <cmath> using namespace std; //using namespace atcoder; using ll = long long; #define all(A) A.begin(),A.end() using vll = vector<ll>; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) using Graph = vector<vector<ll>>; int main() { ll N; string S; ll mod=998244353; cin>>N>>S; vector<vector<vll>> DP(N+1,vector<vll> (26,vll(26,0))); if(N==1){ if(S[0]=='?')cout<<26<<endl; else cout<<1<<endl; return 0; } if(S[0]=='?'){ if(S[1]=='?'){ rep(i,26)rep(j,26) { if(i==j)continue; DP[2][i][j]=1; } } else{ rep(i,26){ if(S[1]-'a'==i)continue; DP[2][i][S[1]-'a']=1; } } } else{ if(S[1]=='?'){ rep(i,26){ if(S[0]-'a'==i)continue; DP[2][S[0]-'a'][i]=1; } } else{ if(S[0]==S[1]){ cout<<0<<endl; return 0; } DP[2][S[0]-'a'][S[1]-'a']=1; } } for(ll n=2;n<S.size();n++){ if(S[n]=='?'){ rep(i,26){ rep(j,26){ if(i==j)continue; rep(k,26){ if(i==k||j==k)continue; DP[n+1][j][k]+=DP[n][i][j]; DP[n+1][j][k]%=mod; } } } } else{ rep(i,26){ rep(j,26){ if(i==j)continue; if(i==S[n]-'a')continue; if(j==S[n]-'a')continue; DP[n+1][j][S[n]-'a']+=DP[n][i][j]; DP[n+1][j][S[n]-'a']%=mod; } } } } ll an=0; rep(i,26){ rep(j,26){ if(i==j)continue; an+=DP[N][i][j]; } } cout<<an%mod<<endl; }