Submission #69686349

---

Source Code Expand

/*
Original Python code (must be included at the beginning of submission):

from collections import *

N = int(input())
S = list(input().rstrip())
N2 = 1 << N
dp = [0] * N2
dp[0] = 1
mod = 998244353
value = [0] * N2
for s in range(1, N2):
    temp = ""
    for i in range(N):
        if (s >> i) & 1 == 0:
            continue
        temp += S[i]
    value[s] = temp

memo = defaultdict(int)
for s in range(1, N2):
    v = value[s]
    if v in memo:
        dp[s] = memo[v]
        continue

    SS = set()
    for i in range(N):
        if (s >> i) & 1 == 0:
            continue
        if value[s ^ (1 << i)] in SS:
            continue
        SS.add(value[s ^ (1 << i)])
        ns = s ^ (1 << i)
        dp[s] += dp[ns]
        dp[s] %= mod
    memo[v] = dp[s]

print(dp[-1])
*/

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    if (!(cin >> N)) return 0;
    string S;
    cin >> S; // the string of length N

    int N2 = 1 << N;
    const long long mod = 998244353LL;

    vector<long long> dp(N2, 0);
    dp[0] = 1;

    vector<string> value(N2);
    for (int s = 1; s < N2; ++s) {
        string temp;
        temp.reserve(N); // small optimization
        for (int i = 0; i < N; ++i) {
            if (((s >> i) & 1) == 0) continue;
            temp.push_back(S[i]);
        }
        value[s] = std::move(temp);
    }

    unordered_map<string, long long> memo;
    memo.reserve(N2 / 2);

    for (int s = 1; s < N2; ++s) {
        const string &v = value[s];
        auto it = memo.find(v);
        if (it != memo.end()) {
            dp[s] = it->second;
            continue;
        }

        unordered_set<string> SS;
        SS.reserve(N);
        long long sum = 0;
        for (int i = 0; i < N; ++i) {
            if (((s >> i) & 1) == 0) continue;
            const string &prev = value[s ^ (1 << i)];
            if (SS.find(prev) != SS.end()) continue;
            SS.insert(prev);
            int ns = s ^ (1 << i);
            sum += dp[ns];
            if (sum >= mod) sum -= mod * (sum / mod);
        }
        sum %= mod;
        dp[s] = sum;
        memo.emplace(v, sum);
    }

    cout << dp[N2 - 1] << '\n';
    return 0;
}

Submission Info

Judge Result