五边形数

Published: December 20, 2020 by Daltao

• Categories:
• algorithm 101

• 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})$计算出来。

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

提供一道题目。