整数拆分问题

题

定义拆分 $p(n)$p(n) 为满足 $\sum_{x \in S}x = n$∑x∈S​x=n 的正整数集合 $S$S 的个数。
输入 $n$n ，求 $p(n) \mod 998244353$p(n)mod998244353 的值。
$n \le 2\times 10^5$n≤2×105。

拆分数定理

记 为 的无序拆分数，则 的生成函数

$F(x) = (1+x+x^2+x^3+x^4+x^5+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+...)(1+x^4+x^8+...)...$F(x)=(1+x+x2+x3+x4+x5+...)(1+x2+x4+x6+...)(1+x3+x6+...)(1+x4+x8+...)...

将其化简

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

最后的那个就是定理的内容。

这个式子可能看起来不是那么直观，这里稍作说明（非常不严谨的）。

拆分数定理的解释

设 $g(x,i)=\sum_{j=0}^\infty x^{ij}$g(x,i)=j=0∑∞​xij

那么

$F(x)=\prod_{i=1}^\infty g(x,i)$F(x)=i=1∏∞​g(x,i)

考虑将这个式子展开，

对于每个 $g(x,i)$g(x,i) ，我们都要选一项乘起来，得到 $x^n$xn 这一项的系数。

那这个系数是多少呢？假设我们从 $g(x,i)$g(x,i) 中选了 $x^{k_i i}$xki​i 这一项，那么

$\prod_{i=1}^n x^{k_i i} = x^n$i=1∏n​xki​i=xn

$\sum_{i=1}^n k_i i = n$i=1∑n​ki​i=n

其中 $\forall i，k_i \in N$∀i，ki​∈N。

现在就非常显然了：$x^n$xn 前的系数就是满足上式的序列 $\{k_i\}${ki​} 的个数，

即我们从 $\{1,2,3,..,n\}${1,2,3,..,n} 中选任意个数使得它们和为 $n$n 的方案数，也就是 $p(n)$p(n)。

五边形数定理

现在我们要对生成函数幂级数展开，这里又有个关于欧拉函数展开项的定理。

$\phi(x)=\sum_{i=-\infty}^\infty (-1)^i x^{\frac{i(3i-1)}{2}}$ϕ(x)=i=−∞∑∞​(−1)ix2i(3i−1)​

五边形数定理证明

这个证明参考了 CSDN Blog @visit_world 的博文：https://blog.csdn.net/visit_world/article/details/52734860

首先考虑欧拉函数的另一个意义：
设 $t(n)$t(n) 为将 $n$n 拆分为偶数个互异的正整数方案数与将 $n$n 拆分为奇数个互异的正整数方案数之差，则欧拉函数为其生成函数。

对于一个拆分方案，
我们记 $k$k 为拆分方案序列中数的个数，$x$x 为其拆分方案中的最小数，$y$y 为对序列中最大数做 操作1 后被标记的数的个数。

若 $x > y$x>y，
我们就对其执行 操作1 ，然后令每个被标记的数 $-1$−1，并在方案序列末尾添上 $y$y 这个数。
如 $20=7+6+4+3$20=7+6+4+3 经操作后就变成 $20=6+5+4+3+2$20=6+5+4+3+2。

若 $x \le y$x≤y，
我们就将方案序列中的 $x$x 删去，然后对序列中最大数进行 操作2 ，并将所有被标记的数 $+1$+1。

操作1：将该数标记，然后看方案中是否有比自己小 $1$1 的数，若有，对其做相同的操作。
操作2：将该数标记，然后看方案中是否有比自己小的数，若有并且当前被标记的数的个数 $&lt; x$<x，对其做相同的操作。

对于任意一个拆分方案，进行完上述操作后，都会使其改变拆分数的个数的奇偶性，除了以下两种特例。

1. x=y 且 操作1 能标记方案中的所有数。
   如 $12=5+4+3$12=5+4+3，操作后变为 $12=6+5+1$12=6+5+1，末尾从没有被添加了 $1$1，因此没有改变奇偶性。如 $12=5+4+3$12=5+4+3，操作后变为 $12=6+5+1$12=6+5+1，末尾从没有被添加了 $1$1，因此没有改变奇偶性。
   此时有 $k=\sum_{i=0}^{y-1}(y+i)=\frac{3y^2-y}{2}$k=i=0∑y−1​(y+i)=23y2−y​

2. x=y+1 且 操作1 能标记方案中的所有数。
   如 $7=4+3$7=4+3，操作后变为 $7=3+2+2$7=3+2+2，划分数列中出现两个相同的数，不合法。
   此时有 $k=\sum_{i=1}^{y}(y+i)=\frac{3y^2+y}{2}$k=i=1∑y​(y+i)=23y2+y​

因此，除了上述两个特例，其他奇偶的拆分方案都可以一一对应起来，又根据 $t(n)$t(n) 的定义，这些方案会相减而消掉。

而这两个特例恰好都是 $k$k 为广义五边形数的情况。它们无法被消掉，所以会对 $t(n)$t(n) 贡献。

当 $k$k 为偶数时，依照定义为正；当 $k$k 为奇数时，依照定义为负。而 $k$k 的奇偶与 $y$y 的奇偶相同。因此经过符号调整后就有最开始的式子。到此证明完毕。

代码

复杂度 $O(n \sqrt n)$O(nn​)。

#include <cstdio>
#define R register
#define Mod 998244353
int n,f[200001],g[200001];
int main()
{
	scanf("%d",&n);
	
	g[1]=0;f[0]=f[1]=g[2]=1;
	
	for (R int i=3;g[i-2]<=n;i+=2)g[i]=(g[i-2]+3*(i>>1)-1)%Mod;
	for (R int i=4;g[i-2]<=n;i+=2)g[i]=(g[i-2]+3*(i>>1)-2)%Mod;
	
	for (R int i=2;i<=n;++i)
	 for (R int j=2;i-g[j]>=0;++j)
	  f[i]=((j>>1)&1)?(f[i]+f[i-g[j]])%Mod:(f[i]-f[i-g[j]]+Mod)%Mod;
	  
	return !printf("%d",f[n]);
}