题解：AT_abc425_f [ABC425F] Inserting Process

MutU · 2025-09-28 20:19:08 · 题解

容易想到状压。但是连续且字符都相同的一段子串内，无论选哪个都是一样的。

加入限制条件，对于连续且相等一段子串，规定只能从左往右操作。这样可以做到不重不漏。

复杂度 O(n2^n)。

#include<bits/stdc++.h>
using namespace std;
int n,f[1<<24];
string st;
int main(){
    cin>>n>>st;
    f[0]=1;
    for(int i=0;i<(1<<n);i++){
        char lst='6';
        for(int j=0;j<n;j++)
            if(!(i&(1<<j) || st[j]==lst))
                lst=st[j],(f[i|(1<<j)]+=f[i])%=998244353;
    }
    cout<<f[(1<<n)-1];
    return 0;
}