这次 NOI Online 入门组考了一道裸的整数拆分问题。
SF 实在太菜，只会暴力，不会这题的正解。
这个菜鸡决定查些资料，好好研究一下整数拆分问题背后的那些事情。
Warning：阅读本文需要一些生成函数与形式幂级数的相关知识，如果您还不了解的话，推荐先阅读 铃悬的数学小讲堂——生成函数初步。
1 五边形数
五边形数（Pentagonal number）\(p_n\) 大概长这个样子：
简单来说，大概就是一个边长 \(n\)（指边上有 \(n\) 个点）的五边形，里面套一个边长 \(n-1\) 的五边形，以此类推。
从图中很容易看出递推式：\(p_n=p_{n-1}+3n-2\)，边界是 \(p_1=1\)（其实 \(n=1\) 时上述递推式仍然成立，不过考虑它的几何意义还是将 \(n=1\) 当作边界）。
根据这个递推式，很容易得出它的通项式：
$$
\begin{align}
p_n &= p_{n-1}+3n-2\\
&= p_{n-2}+3(n-1)-2+3n-2\\
&= \ldots\\
&= \sum_{i=1}^{n} 3i-2\\
&= \frac{3n^2-n}{2}
\end{align}
$$
五边形数在 OEIS 上的编号是 A000326。
五边形数的性质很多，这里简单列出几条：
- 任何正整数都可以表示为不超过 \(5\) 个五边形数的和（详见 费马多边形数定理）。事实上绝大多数正整数都可以拆分为 \(3\) 个五边形数的和。
- 前 \(n\) 个五边形数的平均数是第 \(n\) 个三角形数。
2 广义五边形数
上面的式子中 \(n\) 的取值是正整数，如果将 \(n\) 的取值范围扩大到全体整数，会不会仍然具有一些优雅的性质呢？
于是我们按照 \(n=0,1,-1,2,-2,3,-3,4,-4,\ldots\) 的顺序代入上面的通项式，得到下面的数列：
$$
0, 1, 2, 5, 7, 12, 15, 22, 26,\ldots
$$
这个数列是在原来五边形数的基础上扩充范围得到的，于是我们称其为广义五边形数。它在 OEIS 上的编号为 A001318。
为了方便，广义五边形数仍然用 \(p_n\) 表示。
广义五边形数和下面要讲到的整数拆分问题有很大联系，我们在下文将会深入探究。
3 五边形数定理
介绍一个新函数：欧拉函数。
（注意：这里的欧拉函数 \(\phi(x)\) 不是数论里的那个欧拉函数 \(\varphi(x)\)）
$$
\phi(x)=\prod_{k=1}^{\infty}(1-x^k)
$$
将这个式子展开（这个展开首先由欧拉完成）：
$$
\prod_{k=1}^{\infty}(1-x^k)=\sum_{k=-\infty}^{\infty}(-1)^k x^{\frac{3k^2-k}{2}}
$$
注意 \(x\) 的次数，正是我们前面提到的广义五边形数。五边形数定理由此得名。
将得到的所有项按升幂排列，得到：
$$
\phi(x)=1-x-x^2+x^5+x^7-x^{12}-x^{15}+\ldots
$$
这个展开式的证明太神仙了，笔者并不会，感兴趣的可以看 visit_world 大爷的博客。
得到这个式子有什么用呢？它和我们接下来要提到的整数拆分问题有很大关系。
4 整数拆分问题
接下来进入重头戏。
我们来回顾一下刚刚结束的 NOI Online 里考到的 这道题：
求将正整数 \(n\) 拆分为若干个正整数的和（允许同一个数使用多次，这里的拆分是无序的，即 \(1+2\) 和 \(2+1\) 等价）的方案数。
本题有很多做法，时间效率不尽相同。下面介绍一种运用生成函数的方法。
下面设 \(p(x)\) 为拆分 \(x\) 的方案数（\(p(x)\) 在 OEIS 上的编号为 A000041）。
考虑 \(p(x)\) 的生成函数，
$$
\sum_{k=0}^{\infty}p(k)x^k=\prod_{k=1}^{\infty}\frac{1}{1-x^k}=\frac{1}{\phi(x)}
$$
用五边形数定理展开一下，整理下式子：
$$
\begin{aligned}
\phi(x)\sum_{k=0}^{\infty}p(k)x^k &= (1-x-x^2+x^5+x^7-\ldots)(1+p(1)x+p(2)x^2+p(3)x^3+\ldots)\\
&= 1
\end{aligned}
$$
现在我们想要求出 \(p(k)\)，或者说，算出 \(x^k\) 前面的系数。
将整个式子展开，得到（展开过程这里略去，感兴趣的读者这里可以自己尝试）：
$$
p(k)-p(k-1)-p(k-2)+p(k-5)+p(k-7)-\ldots=0
$$
（PS：有的人可能对这个过程有点疑惑，这里稍微讲一下。上面的等式成立，意味着 \(x^k\) 的系数（别忘了这里是形式幂级数）在左右两边是相等的。这个等式的左边是上面的式子展开后 \(x^k\) 的系数，右边因为只有常数，所以 \(x^k\) 的系数为零）
广义五边形数再一次出现在我们的式子里了。
根据上面这个式子，我们就可以递推计算 \(p(x)\) 的值了。
因为广义五边形数是 \(O(n^2)\) 的级别（不知道的，请翻到最上面看通项式），因此递推式共有 \(O(\sqrt n)\) 项，这样计算的时间复杂度便是 \(O(n \sqrt n)\)。
嗯，代码实现挺短的：
#include <iostream>
using namespace std;
long long f[100005];
int a(int x)
{
return (3*x*x-x)/2;
}
int main()
{
int n,p;
cin>>n>>p;
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=1;;j++)
{
int x=a(j),y=a(-j);
if(x<=i)
f[i]=((f[i]+(j&1?1:-1)*f[i-x])%p+p)%p;
if(y<=i)
f[i]=((f[i]+(j&1?1:-1)*f[i-y])%p+p)%p;
if(x>i||y>i)break;
}
cout<<f[n]<<endl;
return 0;
}