結果

問題 No.1646 Avoid Palindrome
コンテスト
ユーザー kuc_jackson
提出日時 2021-08-14 09:57:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 899 ms / 3,000 ms
コード長 1,382 bytes
コンパイル時間 2,281 ms
コンパイル使用メモリ 200,152 KB
最終ジャッジ日時 2025-01-23 21:47:10
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

int main(){
    const ll mod = 998244353;
    int N; cin >> N;
    string S; cin >> S;
    if(N == 1){
        if(S[0] == '?')cout << 26 << endl;
        else cout << 1 << endl;
        return 0;
    }
    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(26, vector<ll>(26)));
    for(int i = 0; i < 26; i++){
        if(S[0] != '?' && S[0] != 'a' + i)continue;
        for(int j = 0; j < 26; j++){
            if(i == j)continue;
            if(S[1] != '?' && S[1] != 'a' + j)continue;
            dp[2][i][j] = 1;
        }
    }
    for(int i = 2; i < N; i++){
        for(int j = 0; j < 26; j++){
            if(S[i - 1] != '?' && S[i - 1] != 'a' + j)continue;
            ll sum = 0;
            for(int k = 0; k < 26; k++){
                sum = (sum + dp[i][k][j]) % mod;
            }
            for(int k = 0; k < 26; k++){
                if(j == k)continue;
                if(S[i] != '?' && S[i] != 'a' + k)continue;
                ll p = (mod + sum - dp[i][k][j]) % mod;
                dp[i + 1][j][k] = (dp[i + 1][j][k] + p) % mod;
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < 26; i++){
        for(int j = 0; j < 26; j++){
            ans = (ans + dp[N][i][j]) % mod;
        }
    }
    cout << ans << endl;
}
0