P12472 [集训队互测 2024] 基础 ABC 练习题

给定两个集合 $S_1,S_2$，定义一个长度为 $3n$ 且仅包含 `ABC` 三种字符的串 $s$ 是好的，当且仅当存在一种方案将 $s$ 划分成 $n$ 个长度为 $3$ 的子序列，且这 $n$ 个子序列都是 `ABC`，`BCA` 或 `CAB`。设 $n$ 个子序列中 `ABC` 的个数为 $x$，`BCA` 的个数为 $y$，还要求 $x\in S_1,y\in S_2$。 现在有一个长度为 $3n$ 的字符串 $s$，字符串中仅包含 `ABC?` 四种字符，你需要计算将所有 `?` 都分别替换成 `ABC` 三个字符中的某一个的方案，使得串 $s$ 是好的。 对 $2^{32}$ 取模。

**本题单个测试点内有多组测试数据** 第一行两个整数 $T,id$，表示数据组数和子任务编号，保证 $T=60,id\in[0,5]$，$id=0$ 表示是样例。 对于每组数据，第一行一个整数 $n$。 第二行一个长度为 $n+1$ 的 01 串 $s_1$。若 $s_1$ 中第 $i$ 个字符为 $1$，则表示 $S_1$ 中含有 $i-1$ 这个元素，否则不含。第三行以同样的格式刻画 $S_2$。 第四行一个长度为 $3n$ 的字符串 $s$。 对于第 $i$ 组数据，保证 $n=i$。

对于每组数据，输出一行一个整数，表示答案。 **你可以选择是否回答每组数据，详情见说明部分**。

### 样例解释 1 这个样例不满足 $T=60$ 的限制，仅为理解题意用。 ### 样例 2,3 见下发文件，分别满足子任务 1,2 的性质。 ### 提示与说明 | Subtask | 分值 | 特殊限制 | | ------- | ---- | ------------------------------------------------------------ | | 1 | $20$ | $s$ 中没有 `?`，且 $ \left\vert S_1\right\vert=\left\vert S_2\right\vert=n+1 $ | | 2 | $20$ | $s$ 中没有 `?` | | 3 | $10$ | $s$ 中只有 `?`，且 $ \left\vert S_1\right\vert=\left\vert S_2\right\vert=n+1 $ | | 4 | $20$ | $ \left\vert S_1\right\vert=\left\vert S_2\right\vert=n+1 $ | | 5 | $30$ | 无特殊限制 | 对于所有数据，保证 $T=60$。对于每个测试点内的第 $i$ 组测试数据，保证 $n=i$。 ~~测试时开启所有合理的子任务依赖。~~ 子任务依赖尚未配置。 对于每个测试点内的每组测试数据，如果你不打算回答这组测试数据，请输出 $-1$。否则输出一个整数表示答案。如果格式不正确不保证能得到对应的分数。 对于每个测试点，会根据你的输出给出你在这组数据上的评分系数 $p\in [0,1]$。每个 Subtask 的得分是这个 Subtask 中所有测试点得分系数的最小值乘以这个 Subtask 的分值。 首先，你的程序需要正常结束并且所有你选择回答的答案均正确，否则 $p=0$。 在此基础上，记 $d$ 为在所有数据中你的程序选择回答的最大的 $n$，则有 $$ p= \begin{cases} \frac{1}{20} d && d\leq 5 \\ \frac{1}{4}+\frac{1}{50}(d-5) && d\leq 15 \\ \frac{9}{20}+\frac{3}{200}(d-15) && d\leq 35 \\ \frac{3}{4}+\frac{1}{100}(d-35) && d\leq 60 \end{cases} $$ $p$ 与 $d$ 的大致图像如下图所示。