2013 Multi-University Training Contest 5 Partition

思路：五边形数定理！！！

五边形数定理是一个由欧拉发现的数学定理，描述欧拉函数展开式的特性。欧拉函数的展开式如下：

$prod_{n=1}^infty (1-x^n)=sum_{k=-infty}^infty(-1)^kx^{k(3k-1)/2}=sum_{k=0}^infty(-1)^kx^{k(3kpm 1)/2}.$

亦即

$(1-x)(1-x^2)(1-x^3) cdots = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + cdots.$

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

若将上式视为幂级数，其收敛半径为1，不过若只是当作形式幂级数（formal power series）来考虑，就不会考虑其收敛半径。

欧拉函数的倒数是分割函数的母函数，亦即：

$frac{1}{phi(x)}=sum_{k=0}^infty p(k) x^k$

其中 $p(k)$ 为k的分割函数。

上式配合五边形数定理，可以得到

$(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + cdots)(1 + p(1)x + p(2)x^2 + p(3)x^3 + cdots)=1$

考虑 $x^n$ 项的系数，在 n>0 时，等式右侧的系数均为0，比较等式二侧的系数，可得

$p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) + cdots=0$

因此可得到分割函数p(n)的递归式

$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + cdots$

以n=10为例

$p(10) = p(9) + p(8) - p(5) - p(3) = 30 + 22 - 7 - 3 = 42$

这就是所求的了，当n<0时，p(n)=0;

p(n)的其他性质：

当限定将 $n$ 表示成刚好 $k$ 个正整数之和时，可以表示为 $p_k(n)$ 。显然， $p(n) = sum_{k=1}^{n} p_k(n)$ 。

对于 $n>1$ ， $p_n(n) = p_1(n) = 1$
$p_2(n) = lfloor frac{n}{2} floor$ (OEIS:A004526)
$p_3(n)$ = 最接近 $frac{n^2}{12}$ 的正整数。(OEIS:A069905)
$p_{n-1}(n) = C(n,2)$
$p_k(n) = p_{k-1}(n-1) + p_k(n-k)$

代码如下：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<string>
 7 #include<vector>
 8 #define ll __int64
 9 #define pi acos(-1.0)
10 #define MAX 100001
11 using namespace std;
12 const int mod=1000000007;
13 int an[MAX],n,t;
14 void init(){
15     int i,j;
16     an[0]=an[1]=1;
17     an[2]=2;an[3]=3;an[4]=5;
18     an[5]=7;
19     for(i=6;i<MAX;i++){
20         an[i]=0;
21         for(j=1;;j++){
22             int g=j*(3*j-1)/2;
23             if(i-g<0) break;
24             if(j&1) an[i]+=an[i-g];
25             else an[i]-=an[i-g];
26             an[i]=an[i]%mod;
27             while(an[i]<0) an[i]+=mod;
28             g=j*(3*j+1)/2;
29             if(i-g<0) break;
30             if(j&1) an[i]+=an[i-g];
31             else an[i]-=an[i-g];
32             an[i]=an[i]%mod;
33             while(an[i]<0) an[i]+=mod;
34         }
35         an[i]%=mod;
36     }
37 }
38 int main(){
39     init();
40     scanf("%d",&t);
41     while(t--){
42         scanf("%d",&n);
43         printf("%d
",an[n]);
44     }
45     return 0;
46 }

View Code

2013 Multi-University Training Contest 5 Partition

当限定将表示成刚好个正整数之和时，可以表示为。显然，。

当限定将 $n$ 表示成刚好 $k$ 个正整数之和时，可以表示为 $p_k(n)$ 。显然， $p(n) = sum_{k=1}^{n} p_k(n)$ 。