[AGC058D] Yet Another ABC String
Atcoder：[AGC058D] Yet Another ABC String
洛谷：[AGC058D] Yet Another ABC String
Problem
给出 \(a,b,c\)，求由 \(a\) 个 A，\(b\) 个 B，\(c\) 个 C 构成的字符串数量，使得不存在子串 ABC，BCA 和 CAB。\(1 \leq a,b,c \leq 10^6\)。
Solution
可能是 OI 生涯做过最神仙的容斥。
对 极长 非法子串（以下简称非法子串）个数进行容斥，容易发现，非法子串一定形如 ...BCABCABCABCAB... 的循环形式。也就是说，如果一个非法子串的长度和末尾字符确定，该子串就可以被唯一确定。
我们以一个非法子串的最后三位确定其位置。取末三位是为了在计算时保证该位置一定作为非法子串的结尾。
记 \(n = a + b + c, m = n - 3i\)。枚举非法子串数量 \(i\)，然后先确定不是非法子串末三位的其它字符，方案数为 \(\binom{m}{a - i, b - i, c - i}\)。
然后确定这 \(i\) 个末三位的位置，以及进一步算出 钦定 \(i\) 个非法子串的方案数。
假设一个末位置为 \(p\)，如果 \(s_p\) 存在一个后继 \(s_{p + 1}\)，则 \(s_p\) 与 \(s_{p + 1}\) 存在限制，即 \(A\) 后不能接 \(B\)，\(B\) 后不能接 \(C\)，\(C\) 后不能接 \(A\)，否则就无法满足 极长 的条件。在一种确定的插入方案下，对于有后继的非法子串末位置，其后继是确定的，故末位置的填法有 \(2\) 种，对应这个非法子串的方案有 \(2\) 种。相应地，如果非法子串的末位置没有后继，那这个子串就有 \(3\) 种方案。
上述仅考虑了非法子串的末尾字符对非法子串方案数的影响。考虑非法子串的长度，可以反过来将所有非法子串的末位置确定，而剩下的 \(n - 3i\) 的所有情况，可以将非法子串的长度取遍。
总结一下非法子串的方案数，为：\(\binom{m + i - 1}{m - 1}\times 2^{i} + \left( \binom{m + i}{m} - \binom{m + i - 1}{m - 1} \right) \times 2^{i - 1}\times 3\)。简单插板法，略去说明。
总答案为：
\[\begin{aligned} Ans = \sum\limits_{i = 0}^{\min(a, b, c)}(-1)^i\times \binom{m}{a - i, b - i, c - i}\times \end{aligned} \left( \binom{m + i - 1}{m - 1}\times 2^{i} + \left( \binom{m + i}{m} - \binom{m + i - 1}{m - 1} \right) \times 2^{i - 1}\times 3 \right) \] 标签：子串,ABC,非法,times,AGC058D,binom,Yet From： https://www.cnblogs.com/Schucking-Sattin/p/17688417.html