题解

思路

一个字符串能被完全删除，当且仅当 A、B、C 的出现次数奇偶性全部相同：删除两个相同字符不改变奇偶性，三种字符各删一个会同时翻转三种奇偶性；反过来，三者全偶时可成对删除，三者全奇时先各删一个再成对删除。

做法

于是一个连续子串是好字符串，当且仅当它两端的三维前缀奇偶状态相同或互为按位取反。把互为取反的两个状态合并为一类，等价地记录 A 与 B、A 与 C 的计数奇偶差，只剩 4 类前缀状态。若四类在 $N+1$ 个前缀中分别出现 $c_0,c_1,c_2,c_3$ 次，好子串总数就是 $\sum_{j=0}^3\binom{c_j}{2}$。

从左到右做动态规划，状态记录当前前缀所属的类，以及类 1、2、3 已出现的次数；类 0 的次数由前缀总数减去其余三类得到。每遇到固定字符只转移一次，遇到 ? 则分别按 A、B、C 转移。处理完全部字符后，根据四类次数计算好子串数并累加不小于 $K$ 的状态。

复杂度

状态数在所有层合计为 $O(N^4)$，使用滚动数组后空间复杂度为 $O(N^3)$，所有运算均对 $998244353$ 取模。