题解

思路

依次扫描字符串，并同时维护四类总数：已经生成的字符串方案数、所有方案中子序列 a 的总数、子序列 ab 的总数，以及子序列 abc 的总数。

记这四个量为 $f_0,f_1,f_2,f_3$。开始时只有空字符串这一种方案，所以 $f_0=1$，其余均为 $0$。

做法

• 遇到 a：每个已有方案都能在末尾新增一个 a，故 $f_1\leftarrow f_1+f_0$。
• 遇到 b：每个已有的 a 都能扩展成一个 ab，故 $f_2\leftarrow f_2+f_1$。
• 遇到 c：每个已有的 ab 都能扩展成一个 abc，故 $f_3\leftarrow f_3+f_2$。
• 遇到 ?：它有三种替换。原有的每类子序列都会在三种替换中各保留一次；替换成目标字符时又会产生新的扩展。因此按旧值同时更新：$$\begin{aligned} f_3'&=3f_3+f_2,\\ f_2'&=3f_2+f_1,\\ f_1'&=3f_1+f_0,\\ f_0'&=3f_0. \end{aligned}$$

所有运算均对 $10^9+7$ 取模，最终输出 $f_3$。

子任务 1

当 $n\le9$ 时，可以枚举每个问号的三种替换，再枚举三个下标判断是否构成 abc。复杂度为 $O(3^n n^3)$。

子任务 2

当问号数 $k\le4$ 时，可以枚举 $3^k$ 种替换；每次线性扫描统计 abc 子序列。复杂度为 $O(3^k n)$。

子任务 3

使用上述四状态递推，一次扫描即可处理全部数据。

正确性证明

扫描任意前缀后，$f_i$ 分别等于所有该前缀替换方案中，长度为 $i$ 的目标前缀（空串、a、ab、abc）子序列总数。

固定字符只会让恰好以前一状态结尾的子序列多一种扩展，其他已有子序列全部保留，因此三个固定字符的转移正确。问号的三种替换分别产生三份原有子序列，并且仅当替换为当前目标字符时从前一状态产生新增扩展，所以四条问号转移也正确。由数学归纳法，该不变量对每个前缀成立；扫描完整个字符串后，$f_3$ 正是题目要求的总数。

复杂度

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。