题解好像哪里都没说清楚。。。我稍微写一写。。。
首先,按照 3 次方的基本套路,就是枚举数字 $a, b, c$
,然后假设 $a, b, c$
出现了 $x, y, z$
次,把答案加上(至少有 $x$
个 $a$
,至少有 $y$
个 $b$
,至少有 $z$
个 $c$
的划分数)。如果 $a, b, c$
都不同的话,那么这个就是 $n - ax - by - cz$
的划分数,可以用五边型数定理预处理(有重复怎么办,后面再说)。
上面计数的正确性是因为一个恰好有 $x, y, z$
个 $(a, b, c)$
的划分方案被数了$xyz$
次。
所以,关键就是求出多项式:
$\sum_{a \neq b, b \neq c, a \neq c, i, j, k} x^{ia + jb + kc} + 3 \sum_{a = b \neq c, i, j, k} x^{a\max\{i, j\} + ck} + \sum_{a = b = c, i, j, k} x^{a \max\{i, j, k\}}$
接下来就需要使劲了。。。第一项是
$\sum_{a, b, c, i, j, k} - 3\sum_{a = b, c, i, j, k} + 2\sum_{a = b= c} = (\sum_{a, i} x^{ai})^3 - 3 (\sum_{a, i, j} x^{a(i + j)})(\sum_{a, i} x^{ai}) + 2\sum_{a, i, j, k} x^{a(i + j + k)}$
第二项是
$3 (\sum_{a = b, i, j} x^{a\max\{i, j\}} )(\sum_{c, k} x^{ck}) - 3\sum_{a = b = c, i, j, k} x^{a(\max\{i, j\} + k)}$
第三项就是第三项。。
接下来整理一下。。$\sum_{a, i} x^{ai} = \sum_{k} x^k (\sum_{d | k} 1)$
.
然后 $\sum_{a = b, i, j} x^{a\max\{i, j\}} - \sum_{a, i, j} x^{a(i + j)} = \sum x^k (\sum_{d | k} (2d - 1) - (d - 1))$
最后一个还是比较复杂。。。
$\sum_{a, i, j, k} x^{a(i + j + k)} = \sum_{k} x^k (\sum_{d | k} \binom{d - 1}{2})$
.
$\sum_{a, i, j, k} x^{a(\max\{i, j\} + k)} = \sum_{i} x^i (\sum_{d | i} \sum_{m = 1}^{d - 1} (2m - 1)) = \sum_{i} x^i (\sum_{d | i} (d - 1)^2)$
$\sum_{a, i, j, k} x^{a \max\{i, j, k\}} = \sum_{i} x^i (\sum_{d | i} d^3 - (d - 1)^3) $
加起来就是 $\sum_{i} x^i (\sum_{d | i} d^2)$
颇有一种环绕地球三圈半的感觉。。。我找找有没有更简单的路径