AT_abc425_f [ABC425F] Inserting Process 题解

// Problem: Inserting Process
// Contest: Virtual Judge - AtCoder
// URL: https://vjudge.net/problem/AtCoder-abc426_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// Created Time: 2025-10-14 18:53:05
// Author: hjqhs
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
typedef long long ll;
typedef unsigned long long ull;
const int N = 23;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int n, f[1 << N];
string s;
void solve() {
	cin >> n >> s; f[(1 << n) - 1] = 1;
	per(i, (1 << n) - 1, 0) {
		char lasc = ' ';
		rep(j, 0, n - 1) {
			if((i >> j) & 1) {
				if(s[j] != lasc) f[i ^ (1 << j)] = (f[i ^ (1 << j)] + f[i]) % MOD;
				lasc = s[j];
			}
		}
	}
	cout << f[0] << '\n';
	return;
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	// cin >> T;
	while(T --) solve();
	return 0;
}