只做梳理，不做证明 （因为不会证）

五边形数

图片摘自百度百科。

可以发现，$g_i=g_{i-1}+3(i-1)+1$，所以通项就是 $g_i=\frac{i(3i-1)}{2}$

而广义的五边形数，$i$的取值为 $0,1,-1,2,-2,3,-3…$，广义五边形数的前几项为：$0,1,2,5,7,12,15,22,26…$

欧拉函数

著名的欧拉函数 $\phi(x)$，表示比 $x$小的与 $x$互质的数字个数，写出它的生成函数，经过一些奥妙重重的推理，有：

$$\phi(x)=\prod_{i=1}^n (1-x^i)$$

然后经过一些奥妙重重的推理，有：

$$\phi(x)=\sum_{-inf}^{inf} (-1)^i x^{\frac{i(3i-1)}{2}}$$

即

$$\phi(x)=1-x-x^2+x^5+x^7-x^{12}-x^{15}+…$$

拆分数

拆分数 $P(x)$，就是把 $x$拆分成若干个正整数的方案数。例如对于 $3$，有拆分 $3=1+1+1$，$3=1+2$，$3=3$三种，所以 $P_3=3$

利用 1 取多少个，2 取多少个，3 取多少个，这样的思想，得到：

$$P(x)=\prod_{i=1}^{inf}(\sum_{j=0}^{inf} x^{ij})=\prod_{i=1}^{inf}\frac{1}{1-x^i}$$

即 $P(x)\phi(x)=1$

暴力展开，除了 0 次项以外，每一项的系数都要为 $0$，所以对于任意一个 $n$，有：

$P_n-P_{n-1}-P_{n-2}+P_{n-5}+P_{n-7}-P_{n-12}-P_{n-15}+…=0$

由于五边形数的大小是平方级别的，所以我们可以在 $O(n \sqrt{n})$的时间内算出 $1$到 $n$的五拆分数。

代码

HDU4651

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=1000000007,N=100000;
int qm(int x) {return x>=mod?x-mod:x;}
int js,n,T,f[N+5],g[N+5];
int main()
{
    for(RI i=1;;++i) {
        if(i*(3*i-1)/2<=N) g[++js]=i*(3*i-1)/2;
        else break;
        if(i*(3*i+1)/2<=N) g[++js]=i*(3*i+1)/2;
        else break;
    }
    f[0]=1;
    for(RI i=1;i<=N;++i) {
        for(RI j=1;j<=js&&g[j]<=i;++j)
            if(((j+1)/2)&1) f[i]=qm(f[i]+f[i-g[j]]);
            else f[i]=qm(f[i]-f[i-g[j]]+mod);
    }
    scanf("%d",&T);
    while(T--) scanf("%d",&n),printf("%d\n",f[n]);
    return 0;
}

有限制的拆分数

要求拆分后，每一种数字不能用大于等于 $k$次。

那么写出生成函数：

$$\prod_{i=1}^{inf} (1+x^i+x^{2i}+…+x^{(k-1)i})=\prod_{i=1}^{inf} \frac{1-x^{ki}}{1-x^i}=\frac{\phi(x^k)}{\phi(x)}$$

所以这个生成函数 $F(x)$满足（$P(x)$还是指拆分数的生成函数）：$F(x)=P(x)\phi(x^k)$

同样，暴力展开卷积，则有：$f_x=P_x-P_{x-k}-P_{x-2k}+P_{x-5k}+P_{x-7k}-P_{x-12k}-P_{x-15k}+…$

还是可以 $O(n \sqrt{n})$地做。

另外有一个奥妙重重的结论，就是拆分成的数都是奇数的方案数，等于拆分成完全不同的数（也就是每一种数使用不超过 1 次）的方案数。

代码

HDU4658

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=1000000007,N=100000;
int qm(int x) {return x>=mod?x-mod:x;}
int js,n,K,T,f[N+5],g[N+5];
int main()
{
    for(RI i=1;;++i) {
        if(i*(3*i-1)/2<=N) g[++js]=i*(3*i-1)/2;
        else break;
        if(i*(3*i+1)/2<=N) g[++js]=i*(3*i+1)/2;
        else break;
    }
    f[0]=1;
    for(RI i=1;i<=N;++i) {
        for(RI j=1;j<=js&&g[j]<=i;++j)
            if(((j+1)/2)&1) f[i]=qm(f[i]+f[i-g[j]]);
            else f[i]=qm(f[i]-f[i-g[j]]+mod);
    }
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&K);
        int ans=f[n];
        for(RI i=1;i<=js&&g[i]*K<=n;++i)
            if(((i+1)/2)&1) ans=qm(ans-f[n-g[i]*K]+mod);
            else ans=qm(ans+f[n-g[i]*K]);
        printf("%d\n",ans);
    }
    return 0;
}