想要更好的阅读体验？

T2

题意:求和为$n$的本质不同正整数序列数.
$n\le 10^5$
暴力背包有70pts.
做法一:生成函数+五边形数做法:
记答案序列的生成函数为
$$\sum_{i=0}p(i)x^i$$
五边形数定理:
$$ \phi (n)=\prod_{i=1}(1-x^i)=\sum_{i=0}(-1)^ix^{\frac{3k^2\pm k}{2}} $$

$$ \\ \frac{1}{\phi(n)}=\sum_{i=0}p(i)x^i $$

即
$$ (\sum_{i=0}(-1)^ix^{\frac{3k^2\pm k}{2}})\times(\sum_{i=0}p(i)x^i)=1 $$
能对$p(i)$产生贡献的项是$\mathcal O(\sqrt n)$级别的,所以总时间复杂度$\mathcal O(n\sqrt n)$

code
做法二:分块背包:
暴力的做法显然:$f(i,j)$表示用$[1,i]$的数凑出$j$的方案数.转移类似完全背包,时空都是$\mathcal O(n^2)$

考虑取一整数$m$,用$g(i,j)$表示用$i$个不小于$m$的数凑出$j$的方案数.

转移就是整体加一,或加入$m$这个数,即
$$ g(i,j)=g(i-1,j-m)+g(i-1,j-i) $$
显然只有$i\le n/m$的$i$是有意义的,这部分的时间复杂度是$\mathcal O(n/m\times n)$,同时用$f$算用$<m$的数凑出$n$的方案数,总时间复杂度是$\mathcal O((m+n/m)n)$,显然$m=\sqrt n$的时候最优,最优的时空复杂度为$\mathcal O(n\sqrt n)$

code