诈骗题。
实际上答案根本没有破,直接爆搜同一种数组对应的字典序最小字符串即可。
注意在搜索的过程中,需要按的逻辑来搜的,也就是说,一个字符如果在我搜索的过程中被用过了,那么跳的过程中也是不可以用到它的。
#include<bits/stdc++.h>
#define ll long long
#define maxn 10005
#define mod 998244353
using namespace std;
int n;
ll ans=0;
int nxt[maxn],a[maxn];
void dfs(int now)
{
if (now==n)
{
ans++; return;
}
int j=nxt[now],pre=-2;
int used=0;
while (true)
{
if ( ((used>>a[j+1])&1)==0 )
{
used|=(1<<a[j+1]);
nxt[now+1]=j+1;
a[now+1]=a[j+1];
dfs(now+1);
}
if (j==0) break;
j=nxt[j];
}
nxt[now+1]=0; //填了个新字符
a[now+1]=now+1;
dfs(now+1);
}
int main()
{
cin>>n;
dfs(1);
cout<<ans<<endl;
}