Yet Another ABC String AGC058D

[AGC058D] Yet Another ABC String

给定整数 $A$、$B$、$C$。请计算由 $A$ 个 A、$B$ 个 B、$C$ 个 C 组成的字符串 $S$，满足以下所有条件的字符串个数，并将结果对 $998244353$ 取模。

• $S$ 中包含的 A、B、C 的数量分别为 $A$、$B$、$C$。
• $S$ 中不包含 ABC、BCA、CAB 中的任意一个作为子串。

$1\le A,B,C\le 10^6$。

令 $A=0,B=1,C=2$。

首先将限制写下来：

$$\sum_a\prod_i1-[a_i+1\equiv a_{i+1}][a_{i+1}\equiv a_{i+2}][a_{i+2}+1\equiv a_i]$$

发现并不好处理。但是由于限制的形式特殊，即，若 $[i,i+2]$ 不合法，$[i+2,i+4]$ 不合法，则 $[i+1,i+3]$ 也不合法。换句话说，所有不合法的子串会形成很多个极长连续子串。

不妨将 $\prod$ 展开，那么实际上，我们会发现限制变为了若干个 $(-1)^i[a_{l_1}\sim a_{r_1}][a_{l_2}\sim a_{r_2}]\cdots[a_{l_i}\sim a_{r_i}]$，即，我们应该容斥每一个极长连续子串的起点。

设有 $i$ 个起点，那么考虑到我们只需要让每一个字母 $A,B,C$ 都出现一次，于是不妨钦定每一个极长连续子串的长度 $\ge 3$（更长的没有意义，会在容斥种被消掉），这样一共就有 $\binom{A+B+C-3i}{A-i,B-i,C-i}$ 种选择其余自由点的方案。

然后我们再看这些被钦定的起点。由于他们是起点，于是，比方说 ABC，它不能被接在 C 后面，即不能出现 ABC 为起点但是串为 CABC 的情况，这是不合法的。

于是每一个起点都有 $2$ 个选择（特别的，起点有 $3$ 个选择），那么我们分类讨论起点的位置：

• 没有起点位于开头。由于自由元有 $A+B+C-3i$ 个，且没有开头，那么就有 $A+B+C-3i$ 个空隙进行选择，每一个选择里可以有起点，也可以没有。转化为不定方程解数问题后，可以得到 $\binom{i+A+B+C-3i-1}{A+B+C+3i-1}2^i$ 种方案。
• 有起点为开头。那么同理，有 $\binom{i-1+A+B+C-3i}{A+B+C-3i}2^{i-1}\times 3$ 种方案。

最后只需要枚举 $i\in[0,\min\{A,B,C\}]$ 即可。时间复杂度 $\mathcal{O}(n)$ 。