由于一些不可抗拒的原因，\(n\ge 22\) 无解。
那么只用考虑 \(n\le21\) 的情况即可。
由于 \(n\) 的范围缩小，导致状压又可以重新使用，所以考虑状压。
设 \(f_i\) 为 \(i\) 中所有的集合能被表示的最小下标。
那么对于任何一位 \(j\) 如果在 \(i\) 中，那么：
\(f_i=\max(next(f_{i\oplus j},j))\hspace{0.2cm}\text{其中}\hspace{0.1cm}next(x,y)\hspace{0.1cm}\text{表示第一个在}\hspace{0.1cm}x\hspace{0.1cm}\text{后面出现的字符}\hspace{0.1cm} y\hspace{0.1cm}\text{的下标}\)
因为本集合中的所有情况都得满足，所以下标得取最大值。
那么我们只需预处理出来 \(next\) 即可。
从后往前枚举，本位的 \(next\) 可以由上位继承，也要取上一位，设字符串中 \(s_{i+1}\) 为 \(c\) 那么：
\(next_{i,j}=next_{i+1,j}\)
\(next_{i,c}=i+1\)
预处理出来，然后状压 dp，dp 时对每个状态枚举 \(1\) 的位置即可。
详细看代码。
希望有大佬可以指明下为何 \(n\ge22\) 无解。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char s[505];
int n,vis[505][26],f[1<<21];
int main()
{
freopen("factorial.in","r",stdin);
freopen("factorial.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
scanf("%d",&n);
scanf("%s",s+1);
if(n>21)
{
printf("NO\n");
continue;
}
int len=strlen(s+1);
for(int i=0;i<n;i++)vis[len][i]=vis[len+1][i]=len+1;
for(int i=len-1;i>=0;i--)
{
for(int j=0;j<n;j++)vis[i][j]=vis[i+1][j];
vis[i][s[i+1]-'a']=i+1;
}
for(int i=0;i<1<<n;i++)
{
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
f[i]=max(f[i],vis[f[i^(1<<j)]][j]);
}
}
}
if(f[(1<<n)-1]!=len+1)printf("YES\n");
else printf("NO\n");
}
return 0;
}