## 题解的规范
#### 原理
- XXXXX
- YYYYY
#### 方法一
- xxx
- 期望 `30` 分
#### 方法二
- zzzz
- 期望 `60` 分
#### 方法三
- zxzx
- 期望 `100` 分
#### AC 代码
```
int main(){
//代码略
return 0
}
```
### 参考模板
现以 [4745: 跑步](https://oj.nbdp.net/problem.php?id=4745) 为参考
以下为书写的 `markdown` 代码，如果语法不会，可以在这里进行学习
## [学习markdown](https://oj.nbdp.net/tools/markdown.html)
### 特别说明一下
插入代码，要用到两对三个反单引号 (\`) 进行包裹
## *P4745 跑步* 题解
---
这是一题整数拆分的问题
### 方法〇：递归搜索
略
### 方法一：背包
你可以用递归方法，却不能 AC ， 也可以用背包实现，数据太大了
### 方法二：
找规律
1到20循环
$1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627$
由于乎想到母函数，
介绍一个新函数：欧拉函数。
（注意：这里的欧拉函数 $\(\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)\) $。
#### code
```cpp
#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;
}
```
如果你有幸看到这里，上面的代码是如何写出的，以下就是书写内容：除`C++`代码外
---
```markdown
这是一题整数拆分的问题
### 方法〇：递归搜索
略
### 方法一：背包
你可以用递归方法，却不能 AC ， 也可以用背包实现，数据太大了
### 方法二：
找规律
1到20循环
$1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627$
由于乎想到母函数，
介绍一个新函数：欧拉函数。
（注意：这里的欧拉函数 $\(\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)\) $。
```