UOJ #696. 理论复杂度 2022-04-07 22:14 folder 学术

whk 的时候玩出了个直接一点的代数解法，因为只是推导的差别所以一直咕着。今天无聊了来写写（

答案显然是两部分，乘 \(< r\) 的划分数那部分我们按照 Durfee Square 的组合意义随便推个自然求和就行了，那么剩下的就是 \[ \sum_{k\ge 0} \frac{x^{kr}}{(1-x)^2(1-x^2)^2(1-x^k)^2} \]

设 \(\phi(x) = \prod_{k\ge 1} (1-x^k)\)。我们考虑提出 \(\phi^{-2}(x)\) 以简化。并且其实就是乘两次划分数。
现在核心是 \[ \sum_{k\ge 0} x^{kr} (1-x^{k+1})^2(1-x^{k+2})^2 \cdots \]

上面的定义启发我们继续设 \(F(q,x) = \prod_{k\ge 1} (1-qx^k)^2\)，则变成 \[ \sum_{k\ge 0} x^{kr} F(x^k, x) = \sum_{i\ge 0} \frac1{1-x^{i+r}} [q^i] F(q, x) \]

那么同样直接 \(q\)-求导得到自然求和这题就做完了。