P12494 [集训队互测 2024] 数位 DP

小 L 曾经出了这样一个题： > 给定长度为 $4$ 的整数序列 $c$，求是否存在长度为 $4$ 的整数序列 $a$ 满足 $0\le a_i\le c_i$ 且 $(((a_1\text{ and }a_2)\text{ xor }a_3)\text{ or }a_4=m$。 小 C 看到后觉得这个数位 DP 题非常板，很没意思。小 L 又修改上述问题的位运算的顺序，出了很多个题。 小 C 忍不了了：“你能不能别再出模板数位 DP 题了？” 小 L 只能把这一堆题交给了你。不过为了增加挑战性，现在你需要对所有可能的 $c_i$ 计算出答案并求和。

给定长度为 $n-1$ 的字符串 $s$，对于一个长度为 $n$ 的非负整数序列 $a$，定义其生成序列 $b$ 为： - $b_1=a_1$； - 对于 $i>1$： - 若 $s_{i-1}=\verb!A!$，则 $b_i=b_{i-1}\text{ and }a_i$。 - 若 $s_{i-1}=\verb!O!$，则 $b_i=b_{i-1}\text{ or }a_i$。 - 若 $s_{i-1}=\verb!X!$，则 $b_i=b_{i-1}\text{ xor }a_i$。 给定非负整数 $k$。接下来 $q$ 组询问，每次给定一个 $m$，求有多少长度为 $n$ 的整数序列 $c$ 满足： - 对于 $1\le i\le n$，满足 $0\le c_i

第一行三个整数 $n,k,q$。 第二行一个长度为 $n-1$ 的字符串 $s$。 接下来 $q$ 行，每行一个询问的 $m$。

输出 $q$ 行，每行一个非负整数，表示答案对 $2^{32}$ 取模的结果。

**本题使用捆绑测试，你只有通过一个子任务的所有测试点，才能获得这个子任务的分数**。 | 子任务编号 | $n\le$ | $k\le$ | $q\le$ | 特殊性质 | 分值 | | :--------: | :----: | :----: | :----: | :------------------------: | :--: | | $1$ | $4$ | $5$ | $200$ | 无 | $10$ | | $2$ | $20$ | $8$ | $20$ | 无 | $10$ | | $3$ | $200$ | $16$ | $1$ | 无 | $10$ | | $4$ | $200$ | $16$ | $200$ | 无 | $10$ | | $5$ | $200$ | $30$ | $1$ | $\text{popcount}(m)\le 16$ | $10$ | | $6$ | $1000$ | $30$ | $1000$ | $s$ 不包含 $\verb!A!$ | $10$ | | $7$ | $50$ | $30$ | $50$ | 无 | $10$ | | $8$ | $1000$ | $30$ | $1$ | 无 | $10$ | | $9$ | $200$ | $30$ | $200$ | 无 | $10$ | | $10$ | $1000$ | $30$ | $1000$ | 无 | $10$ | 对于 $100\%$ 的数据，$2\le n\le 1000$，$1\le q\le 1000$，$1\le k\le 30$，$0\le m