整数划分的根号算法还没有搞懂...先咕着。

定义一个欧拉函数：

ϕ(x)=∏i=1∞(1−xi)\phi(x)=\prod_{i=1}^{\infty}(1-x^i)

这个不是数论的欧拉函数哦qwq

欧拉函数与整数划分数的关系

欧拉函数的倒数是整数划分数的生成函数。
即

1ϕ(x)=∑i=0∞p(i)xi\frac{1}{\phi(x)}=\sum_{i=0}^{\infty}p(i)x^i

其中 p(i)p(i) 为 ii 划分为若干个正整数之和的方案数。
考虑 p(i)p(i) 的生成函数

∑i=0∞p(i)xi\sum_{i=0}^{\infty}p(i)x^i

这个是把所有数的所有的划分方式求了和。于是可以换一种统计方式

∏i=1∞(1+xi+x2i+… )\prod_{i=1}^{\infty}(1+x^i+x^{2i}+\dots)

化一下等比数列就会发现是欧拉函数的倒数。

五边形数定理

ϕ(x)=∑k=−∞∞(−1)kxk∗(3k−1)2\phi(x)=\sum_{k=-\infty}^{\infty}(-1)^kx^{\frac{k*(3k-1)}{2}}

其中形如 k∗(3k−1)2\frac{k*(3k-1)}{2} 的数叫做五边形数。
考虑欧拉函数的组合意义,它的第 nn 项系数其实就是把 nn 拆成偶数个互不相同的正整数的和的方案数 - 把 nn 拆成奇数个互不相同的正整数的和的方案数。
为何?考虑欧拉函数的每一个单项式，如果选对应的 xix^i，则表示划分出了 ii 这个数，系数乘 −1-1。于是显然。

之后可以对奇数的方案和偶数的方案构造出双射，证明只有五边形数 k+(k+1)+(k+2)+⋯+(2k−1)=k(3k−1)2k+(k+1)+(k+2)+\dots+(2k-1)=\frac{k(3k-1)}{2} 有一种方案不符合双射，且与 kk 奇偶性有关。则得证。具体看这里

于是我们可以根据划分数的生成函数和欧拉函数的卷积直接递推，因为五边形数大小是 n2n^2 级别的，所以可以做到 O(nn)O(n\sqrt n)。模意义下可以NTT求乘法逆，复杂度 O(nlogn)O(nlogn)。

。。整数划分数就是完全背包的模型，可以直接套用论文中取ln和exp的做法做到nlogn。。但是对于一些有限制的整数划分这种做法就无能为力了，还是需要处理出欧拉函数。如hdu4658

失智。。根号算法is easy enough
我们考虑有两种dp的方式。
1.dp[i][j]dp[i][j] 表示用的数都小于等于 ii 和为 jj 的方案数。这是个完全背包模型。
2.dp[i][j]dp[i][j] 表示 ii 个数和为 jj 的方案数。这是通常写的。

我们发现第一个dp状态量与数大小有关，第二个dp状态量与数个数有关。那么根号平衡一下。

我们把数分成小于等于 n\sqrt n 和大于 n\sqrt n 两部分，分别求出只用这两部分的数的方案数。然后再枚举两部分的和都为多少，乘法原理一下就好了。

这样小于等于 n\sqrt n 的部分用1方式求解，状态量 nnn\sqrt n，大于 n\sqrt n 的部分用2方式求解，状态量 nnn\sqrt n，于是完美解决。注意第二个dp时要滚动数组。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50,mod=1e9+7;
int n,sq,f[N],g[N],h[N],gg[N],ans;
int main(){
    scanf("%d%d",&n);sq=sqrt(n);
    f[0]=1;
    for(int i=1;i<=sq;i++)for(int j=i;j<=n;j++)(f[j]+=f[j-i])%=mod;
    g[0]=gg[0]=1;
    for(int i=1;i<=sq;i++){
        memcpy(h,g,sizeof(g));
        memset(g,0,sizeof(g));
        for(int j=i*(sq+1);j<=n;j++)
            g[j]=(h[j-sq-1]+g[j-i])%mod,
            (gg[j]+=g[j])%=mod;
    }
    for(int i=0;i<=n;i++)ans=(ans+1ll*f[i]*gg[n-i])%mod;
    printf("%d\n",ans);
    return 0;
}