自动搬运

查看原文

来自洛谷，原作者为

	Sampson_YW 你弱归你弱，YW比你弱。

搬运于2025-08-24 22:52:37，当前版本为作者最后更新于2023-12-11 10:00:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于一条限制，如果出现了 O，那么就表示这个位置上必须填某个字符。如果出现了 -，那么就可以知道某个字符至少出现了几次，记为 $L_i$。如果出现了 x，那么就可以知道某个字符恰好出现了几次，记为 $R_i$。并且如果某个位置是 - 或 x，那么就表示这个位置上不能填某个字符。

如果有 $L_i>R_i$ 或者 $\sum L_i>k$，那么无解。否则 $\sum L_i\leq k$，可以将这些字符状压成一个长度为 $\sum L_i$ 的二进制位，代表填没填过。每次转移就枚举一个字符，判断一下这个字符能不能填到这个位置上，并且填上之后有是不是仍然满足出现次数的限制，如果两个条件都满足就可以转移。

转移分为：填出现次数小于 $L_i$ 的字符，填出现次数大于等于 $L_i$ 的字符两种。前一种每次转移的枚举次数是 $O(k)$ 的，后一种每次转移的枚举次数是 $O(|\Sigma|)$ 的。

所以直接暴力转移的复杂度是 $O\left((|\Sigma|+k)k2^k\right)$ 的，我没跑过去。对于第二种转移预处理：只考虑出现次数的限制时，能填的字符是哪些。复杂度 $O(k^22^k)$。

code