只做梳理,不做证明 (因为不会证)

五边形数

图片摘自百度百科。

可以发现,$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;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

1 条评论

【题解】 整数划分$O(n sqrt n)$的Naive做法 – MiNa! · 2019年1月15日 10:55 下午

[…] litble 刚刚发了一篇介绍五边形数定理做整数划分,能做到 $O(n sqrt n)$预处理,$O(1)$询问的文章,可以戳这里:https://www.mina.moe/archives/10981 […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注