计算小练习 7（AGC085D）

· · 题解

没活整了，怎么办！

题目链接

我不会容斥，也不会分析性质，我只会暴力递推！

设 f_0 表示以 AA 结尾的合法串数量的三元生成函数（用 x,y,z 分别计量 A,B,C 出现的次数），f_1 表示 AB 结尾的 ... f_8 表示 CC 结尾的。于是就能得到一个 9 元线性方程组：

\\f_4 = y(f_1+f_4+f_7) + y^2 \\f_5 = z(f_4+f_7) + yz \\f_6 = x(f_2+f_8) + xz \\f_7 = y(f_2+f_5+f_8) + yz \\f_8 = z(f_2+f_5+f_8) + z^2 \end{cases}

理解起来很简单，比如 f_5，它表示 BC 结尾的情况。这可以由 BB、CB 结尾的情况接一个 C 组成（注意不能由 AB 拼接 C，因为 ABC 是不能出现的），同时补上缺掉的只有 BC 两项的情况（即那个单项 yz）。

这个方程组中是蕴涵着某种对称性的，我们就可以容易地使用mma算出

\sum_{i=0}^8f_i=\frac{(3-x-y-z)/2}{1-x-y-z+2xyz}-\frac 32-x-y-z

由于 A,B,C \geq 1，我们要算的答案就只是

\frac 12[x^Ay^Bz^C] \frac{3-x-y-z}{1-x-y-z+2xyz} =\frac 12[x^Ay^Bz^C]\sum_{i\geq 0}(-1)^i(2xyz)^i(3-x-y-z)(1-x-y-z)^{-1-i} =\frac 12 \sum_{i\geq 0}(-2)^i [x^{A-i}y^{B-i}z^{C-i}]\left( \frac{2}{(1-x-y-z)^{i+1}}+\frac{1}{(1-x-y-z)^i}\right)

两项有类似的形式，只用考虑其中一部分：

[x^ay^bz^c]\frac{1}{(1-x-y-z)^k}=[x^ay^bz^c]\sum_{i\geq 0}\binom{k+i-1}{k-1}(x+y+z)^i

提取系数后，显然和式中仅有 i=a+b+c 的那一项非零，结果就是

\binom{k+a+b+c-1}{k-1}\binom{a+b+c}{a,b,c}

带回原式，答案即为

\frac 12 \sum_{i \geq 0}(-2)^i \left( 2\binom{A+B+C-2i}{i}+\binom{A+B+C-2i-1}{i-1}\right)\binom{A+B+C-3i}{A-i,B-i,C-i}