范德蒙德卷积

AGC058D – Yet Another ABC String

将 $\mathtt{A,B,C}$ 换成 $0,1,2$。记 $a,b,c$ 是题面中 $\mathtt{A,B,C}$ 的数量，$n=a+b+c$。我们称位置 $i$ 不合法，当且仅当 $S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3$。将其视为两条边 $(i-2,i-1),(i-1,i)$，那么所有不合法的位置造成的连边将会形成若干条链。

考虑容斥。直接钦定指定数量的位置不合法，其方案是难以计算的。又因为容斥系数是 $(-1)^c$，$c$ 为钦定的非法位置数量，那么将整个串分成若干个部分分别计算方案，带上容斥系数相乘后累加，结果不变。故而尝试从上文的链入手：易得对于固定长度的一条链，能够连成它的非法位置集合不变。设 $f(l,0)$ 表示“大小为偶数，且能够连成长度恰为 $l$ 的链”的非法位置集合数量；$f(l,1)$ 则是大小为奇数。染色方案与位置集合方案是独立的；则设整个串按顺序被分成了链 $(l_1,l_2,\cdots,l_s)$（此处的“链”长度均不小于 $3$），答案即为 $$\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right)$$ （更多…）