Submission #75559152

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int mod = 998244353;

int dp[1005][11][11][11];
array<int,3> nxt[11][11][11][26];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<string>s(3);
    for(int i = 0; i<3; i++){
        cin >> s[i];
    }
    dp[0][0][0][0] = 1;
    rep(i,0,sz(s[0])) rep(j,0,sz(s[1])) rep(k,0,sz(s[2])) rep(c,'a','z'+1){
        vi len = {i,j,k};
        rep(x,0,3){
            if(s[x][len[x]] == c){
                len[x]++;
            }
        }
        bool ok = 1;
        rep(x,0,3){
            if(len[x] == sz(s[x]))ok = 0;
        }
        if(!ok){
            nxt[i][j][k][c-'a'] = {-1,-1,-1};
        }
        else{
            nxt[i][j][k][c-'a'] = {len[0],len[1],len[2]};
        }
    }
    rep(t,0,n) rep(i,0,sz(s[0])) rep(j,0,sz(s[1])) rep(k,0,sz(s[2])) rep(c,'a','z'+1) {
        auto [ni,nj,nk] = nxt[i][j][k][c-'a'];
        if(ni == -1 || nj == -1 || nk == -1)continue;
        dp[t+1][ni][nj][nk] += dp[t][i][j][k]; dp[t+1][ni][nj][nk] %= mod;
    }
    int ans = 0;
    rep(i,0,sz(s[0])) rep(j,0,sz(s[1])) rep(k,0,sz(s[2])) {
        ans += dp[n][i][j][k]; ans %= mod;
    }
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result