五边形数

Published: by Creative Commons Licence

  • Tags:

五边形数定理

公式:

\[\prod_{n=1}^\infty(1-x^n)=\sum_{k=-\infty}^\infty(-1)^kx^{k(3k-1)/2}=1+\sum_{k=1}^\infty (-1)^k(x^{k(3k+1)/2}+x^{k(3k-1)/2})\]

问题1:要求计算$\sum_{i=1}^ni\cdot c_i=n$中,$0\leq c_1,\ldots,c_n$,有多少种$c_1,\ldots,c_n$的赋值方案

可以用生成函数求解,我们要求的是$f(x)$的$x^n$项的系数:

\[f(x)=\prod_{i=1}^n(1+x^i+x^{2i}+\ldots)\pmod x^{n+1}=\prod_{i=1}^n\frac{1}{1-x^i}\pmod x^{n+1}\]

可以发现:

\[\frac{1}{f(x)}\pmod x^{n+1}=\prod_{i=1}^n(1-x^i)\pmod x^{n+1}=\prod_{i=1}^\infty(1-x^i)\pmod x^{n+1}\]

这里我们可以利用五边形定理快速求出$\frac{1}{f(x)}\pmod x^{n+1}$,之后求逆即可。

时间复杂度为$O(n\log_2n)$。

问题2:要求计算$\sum_{i=1}^ni\cdot c_i=k$中,$0\leq c_i\leq a_i$,有多少种$c_1,\ldots,c_n$的赋值方案分别满足$k=1,2,\ldots,n$。输入满足$0\leq a_1<a_2<\ldots<a_n$,其中$n\leq 10^5$。

可以用生成函数求解,我们要求的是$f(x)$:

\[f(x)=\prod_{i=1}^n(1+x^i+x^{2i}+\ldots+x^{a_i\cdot i})\pmod x^{n+1}=\prod_{i=1}^n\frac{1-x^{(a_i+1)\cdot i}}{1-x^i}\pmod x^{n+1}\]

由于$0\leq a_1<\ldots <a_i$,因此有$a_i+1\geq i$,故$(a_i+1)\cdot i\geq i^2$。因此$(1-x^{(a_i+1)\cdot i})$中最多$\sqrt{n}$项不为$1$。因此分子部分的乘积和,我们可以$O(n\sqrt{n})$计算出来。

分母部分就是一个典型的五边形定理的应用了。求出来后分子乘上分母的逆多项式即可得到结果。

提供一道题目