P3989 [SHOI2013] 阶乘字符串 题解
ZnPdCo
·
·
题解
题目大意
给定一个字符串，看其是不是 n 个小写字母全排列组成的子序列（注意不是子串）
更新记录
upd:2023-10-02 22:05:50 第一版，提出反例 abcdabcadbac
upd:2023-10-04 21:34:47 第二版，发现更优的构造方法（By @Ac_forever）
首先，我们可以很容易发现，n>21 时完全构造不出合法的方案，所以答案一定为 NO。
证明：然鹅，网上说 \dbinom{450}{21}<21! 是不正确的， 因为我自己算了一遍发现不对。
然后就是所谓的 n^2-n+1 或 n(n-1)+1，是错误的、更优的构造方法为：
设 'a'+n-1 为 x，则重复 n-3 遍从 a 到 x，然后再为 a 到 x-1，再为 a 和 x，再为 a+1 到 x-1，最后为 a。
举个例子可能会更好（n=5）：
\underbrace{abcde\ abcde}_{n-3\text{遍}}\ \underbrace{abcd}_{\text{去尾}}\ \underbrace{a\ e}_{\text{头、尾}}\ \underbrace{bcd}_{\text{去头去尾}}\ \underbrace{a}_{\text{固定了}}
但是我不会证明
但是又有前车之鉴，所以说，只能是最小字符串长度的上限是 n^2-n。
那么我们假定就是这个就是最小字符串的大致范围，那么发现当 n=22 时 n^2-n=462>450，所以当 n>21 时完全构造不出合法的方案。
发现可以状压。
用 f_s 表示进行状态转移，s 表示我们组成的前排列中字母的存在情况。例如 s=(101)_2 表示有字母 a 和 c。
定义函数 $\text{nxt}(i,j)$ 表示第 $i$ 位后面的第一个字符 $j$ 的位置（不含自己）
然后枚举新加入的字符 `c`，易得：
$$
f_{s|c}=\max(f_{s|c},\text{nxt}(f_s,c))\qquad c\not\in s
$$
为什么是 $\max$？因为有两种情况：
1. $f_{s|c} > \text{nxt}(f_s,c)$，那么这时候 $f_{s|c}$ 是包含的 $c$ 的，满足条件
2. $f_{s|c} < \text{nxt}(f_s,c)$，那么这时候 $f_{s|c}$ 是不包含的 $c$ 的，要把 $c$ 包括进去
最后判断 $f_{(\underbrace{111\cdots111}_{\text{(n-1)个1}})_2}$，也就是 $f_{(1<<n)-1}$ 是不是合法的即可。
```c++
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define INF (ll)(1e17)
using namespace std;
ll t;
ll n;
char S[500];
ll nxt[500][26];
ll f[(1<<21)+10];
int main() {
scanf("%lld", &t);
while(t--) {
scanf("%lld", &n);
scanf("%s", S + 1);
ll m = strlen(S + 1);
if(n > 21) {
printf("NO\n");
continue;
}
for(ll c = 0; c < n; c++) nxt[m][c] = INF;
for(ll s = 0; s < (1 << n); s++) {
f[s] = 0;
}
for(ll i = m; i >= 1; i--) {
for(ll c = 0; c < n; c++) {
nxt[i - 1][c] = nxt[i][c];
}
nxt[i - 1][(ll)(S[i]) - 'a'] = i;
}
for(ll s = 0; s < (1 << n); s++) {
for(ll c = 0; c < n; c++) {
if((s | (1 << c)) != s) {
if(f[s] == INF) f[s | (1 << c)] = INF;
else f[s | (1 << c)] = max(f[s | (1 << c)], nxt[f[s]][c]);
}
}
}
if(f[(1 << n) - 1] == INF) printf("NO\n");
else printf("YES\n");
} // ( •̀ ω •́ )\
}
```