五边形数定理

大家好，欢迎来到IT知识分享网。

五边形数定理

五边形数

广义五边形数

广义五边形数的公式和五边形数相同，只是 $n$ 可以为负数和零，$n$ 依序为 $0,1,-1,2,-2,3,-3,4\cdots$ 广义五边形数也可以用下式表示：
$$p_n=\frac{2n^2\pm n}{2}$$
$n$ 依序为 $0,1,2,3,4\cdots$

五边形数定理

欧拉函数展开后，有些次方项被消去，只留下次方项为 $1,2,5,7,12,\cdots$ 的项次，留下来的次方恰为广义五边形数。

整数划分问题

使用正整数相加组合成n的方案数，比如 $4$ 有以下几种：$1+1+1+1,2+2,4,1+3,1+1+2$。

• dp 做法

  设 $dp[i][j]$ 表示使用不大于 $j$ 的正整数来组成 $i$ 的方案数，则状态转移方程为：
  $$\{\begin{array}{ccc}dp[i][j]=dp[i-j][j]+dp[i][j-1]& & i\ge j\\ dp[i][j]=dp[i][i]& & i<j\end{array}$$
  

• 生成函数+五边形数定理

  设 $n$ 的拆分方案数为 $p(n)$ ，则欧拉函数的倒数为分割函数的母函数 $F(x)$ ，即
  $$F(x)=\sum _{i=0}^{\infty }p(i)x^i=\frac{1}{\varphi (x)}=\prod _{i=1}^{\infty }\frac{1}{1-x^i}$$
  证明：对于每一个数 $i$ 考虑选 $0,1,2,3,\cdots$ 次，则生成函数为
  $$g(i)=1+x^i+x^{2i}+\cdots =\frac{1}{1-x^i}$$
  将每一个数的生成函数相乘，得：
  $$F(x)=\prod _{i=0}^{\infty }g(i)=\frac{1}{\varphi (x)}$$
  得证。
  
  
  
  
  
  

  由于上述等式成立，考虑等式两边同乘以 $\varphi (x)$ ，得
  $$F(x)\varphi (x)=1$$
  根据五边形数定理展开得
  $$\sum _{i=0}^{\infty }p(i)x^i(1+\sum _{j=1}^{\infty }(-1{)}^j{x}^{\frac{j(3j\pm 1)}{2}})=1$$
  由于等式右边不含 $x$ ，因此等式左边展开后 $x^k$ 的系数均为 $0$ 。
  
  
  
  

  因此由五边形数定理展开后 $x$ 的幂次为广义五边形数，通过固定展开式中 $x$ 的幂次可以得出如下递推式：
  $$p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots$$
  而上式中 $n$ 减掉的数正是广义五边形数。
  
  

  由于五边形数的增长速度是 $O(n^2)$ ，因此可以 $O(\sqrt{n})$ 枚举五边形数暴力 dp ，总时间复杂度为 $O(n\sqrt{n})$ 。

例题：HDU4651 Partition

求解 $p(n)$ ，方法如上。

const int N = 1e5 + 10, MOD = 1e9 + 7; inline void add(int &x, int y) { 
    x += y; if (x >= MOD) x -= MOD; } inline void sub(int &x, int y) { 
    x -= y; if (x < 0) x += MOD; } int p[600], T, dp[N], n[N], mxn; int main() { 
    scanf("%d", &T); for (int i = 1; i <= T; i++)scanf("%d", &n[i]); mxn = *max_element(n + 1, n + 1 + T); for (int i = 1, j = 1;; i += 2, j++) { 
    p[i] = (3 * j * j - j) >> 1; if (p[i] > mxn)break; p[i + 1] = (3 * j * j + j) >> 1; if (p[i + 1] > mxn)break; } dp[0] = 1; for (int i = 1; i <= mxn; i++) for (int j = 1; p[j] <= i; j++) { 
    if ((j + 1) >> 1 & 1) add(dp[i], dp[i - p[j]]); else sub(dp[i], dp[i - p[j]]); } for (int i = 1; i <= T; i++) printf("%d\n", dp[n[i]]); return 0; } 

例题：HDU4658 Integer Partition

将一个正整数 $n$ 划分为多个正整数的和的方案数，但每个数的使用次数小于 $k$ 次。

const int N = 1e5 + 10, MOD = 1e9 + 7; inline void add(int &x, int y) { 
    x += y; if (x >= MOD) x -= MOD; } inline void sub(int &x, int y) { 
    x -= y; if (x < 0) x += MOD; } int p[600], T, dp[N], n[N], k[N], mxn; int main() { 
    scanf("%d", &T); for (int i = 1; i <= T; i++) scanf("%d%d", &n[i], &k[i]); mxn = *max_element(n + 1, n + 1 + T); for (int i = 1, j = 1;; i += 2, j++) { 
    p[i] = (3 * j * j - j) >> 1; if (p[i] > mxn)break; p[i + 1] = (3 * j * j + j) >> 1; if (p[i + 1] > mxn)break; } dp[0] = 1; for (int i = 1; i <= mxn; i++) for (int j = 1; p[j] <= i; j++) { 
    if ((j + 1) >> 1 & 1) add(dp[i], dp[i - p[j]]); else sub(dp[i], dp[i - p[j]]); } for (int i = 1; i <= T; i++) { 
    int ans = dp[n[i]]; for (int j = 1; 1ll * k[i] * p[j] <= n[i]; j++) { 
    if ((j + 1) >> 1 & 1)sub(ans, dp[n[i] - k[i] * p[j]]); else add(ans, dp[n[i] - k[i] * p[j]]); } printf("%d\n", ans); } return 0; }