P3989 [SHOI2013] 阶乘字符串-526互联

先考虑部分分，看到 \(n \leq 20\) 容易想到这个部分可以用状压
起初可以设 \(dp_{S,i}\) 表示在前 \(i\) 个数中选出集合 \(S\) 中的字母是否可行，转移即枚举下一个字母是什么
这个 dp 有一个很显然的性质：他肯定是前缀一段 \(0\) ，后缀一段 \(1\) 。我们不妨优化一下：设 \(dp_S\) 表示选完集合 \(S\) 中的数的所有情况中距离最远的情况能选择的最近下标是什么。
转移即记录 \(nxt_{i,j}\) 表示从 \(i\) 开始往后选第 \(j\) 个字母的最近距离，可以知道 \(dp_{S} = \max\limits_{x \notin S} \{ nxt_{dp_{S-x}+1,x} \}\)
最终答案即为 \([dp_{2^m-1} \leq n]\)
然后 \(n \leq 26\) 呢？我们发现比较优秀的构造方案是 \(abcdcbabcd \cdots\) 这样，他的长度下界应该是 \(n^2-n+1\) 的。我们发现当 \(n=22\) 时， \(n^2-n+1=463>450\) ，因此我们在 \(n \geq 22\) 时输出 NO 即可
最终复杂度 \(O(T|S|2^{\max(n,\omega)})\) ，其中 \(\omega=21\)