Submission #37903909

---

Source Code Expand

/*
 * File created on 01/09/2023 at 11:50:23.
 * Link to problem: 
 * Description: 
 * Time complexity: O()
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2023 Francois Vogel
*/

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define sz(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int MOD = 998244353;

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    string b;
    cin >> b;
    int dp [n+1][27][27];
    for (int i = 0; i < 27; i++) for (int j = 0; j < 27; j++) dp[n][i][j] = 1;
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < 27; j++) for (int k = 0; k < 27; k++) {
            dp[i][j][k] = 0;
            for (int x = 0; x < 26; x++) if ((b[i] == '?' || b[i] == 'a'+x) && x != j && x != k) {
                dp[i][j][k] += dp[i+1][k][x];
                dp[i][j][k] %= MOD;
            }
        }
    }
    cout << dp[0][26][26];

    cout.flush();
    int d = 0;
    d++;
}

Submission Info

Judge Result