【数论 高等数学】跑步

原题链接

---

部分参考自：https://www.acwing.com/solution/acwing/content/4795/

---

模型：把n拆成若干个正整数的方案数。
拆分时顺序是无所谓的。
n=2+1+1=1+2+1 为一种方案
4=4=3+1=2+2=2+1+1=1+1+1+1 一共五种方案

整数划分问题

缩小n的范围。1<=n<=1000
整数划分
方法一：完全背包
把1~n看作n个物品，每个物品的体积为1，问：装满背包的情况下方案数是多少。

方法二：换一种状态表示 f[i][j]:总和为j，一共有i个数

答案:f[n][1]+f[n][2]+f[n][3]+…+f[n][n]

前两种做法的时间复杂度都为：O(n2)
在 跑步 一题中只可以获得部分分。

---

做法 优化 母函数+五边形数定理

五边形数定理

设划分整数i的方案为$p_i$pi​。得到数列{$p_n$pn​}。
生成函数：$f(x)=p_0+p_1x^1+p_2x^2+...+p_nx^n(0≤x≤1)$f(x)=p0​+p1​x1+p2​x2+...+pn​xn(0≤x≤1)
显然$p_0=1$p0​=1
令$f(x)=(1+x^1+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+..)...$f(x)=(1+x1+x2+...)(1+x2+x4+...)(1+x3+x6+..)...
即：$f(x)=(({x^1})^0+({x^1})^1+({x^1})^2+...)(({x^2})^0+({x^2})^1+({x^2})^2+...)({(x^3})^0+{(x^3)}^1+({x^3})^2+...)...$f(x)=((x1)0+(x1)1+(x1)2+...)((x2)0+(x2)1+(x2)2+...)((x3)0+(x3)1+(x3)2+...)...
$(({x^1})^0+({x^1})^1+({x^1})^2+...)$((x1)0+(x1)1+(x1)2+...):选出几个1
$(({x^2})^0+({x^2})^1+({x^2})^2+...)$((x2)0+(x2)1+(x2)2+...):选出几个2
$({(x^3})^0+{(x^3)}^1+({x^3})^2+...)$((x3)0+(x3)1+(x3)2+...):选出几个3
……
（1代表不选择）

例子：
样例1：
4=4 即 $x^4=1×1×1×x^4=({x^1})^0({x^2})^0({x^3})^0({x^4})^1$x4=1×1×1×x4=(x1)0(x2)0(x3)0(x4)1
4=1+3 即 $x^4=x^1×1×x^3=({x^1})^1({x^2})^0({x^3})^1$x4=x1×1×x3=(x1)1(x2)0(x3)1
4=2+2 即 $x^4=1×x^4=({x^1})^0({x^2})^2$x4=1×x4=(x1)0(x2)2
4=1+1+2 即 $x^4=x^2×x^2=({x^1})^2({x^2})^1$x4=x2×x2=(x1)2(x2)1
4=1+1+1+1 即 $x^4=x^2=({x^1})^4$x4=x2=(x1)4

即：问题转化为求生成函数所有括号乘积组合出的$x^n$xn的情况数。

利用等比数列求和求解：
$(1+x^1+x^2+...)=\frac{x^∞-1}{x-1}=\frac{1}{1-x}$(1+x1+x2+...)=x−1x∞−1​=1−x1​

$(1+x^2+x^4+...)=\frac{x^∞-1}{x^2-1}=\frac{1}{1-x^2}$(1+x2+x4+...)=x2−1x∞−1​=1−x21​
……

所以$f(x)=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}……=\frac{1}{(1-x)(1-x^2)(1-x^3)……}$f(x)=1−x1​1−x21​1−x31​……=(1−x)(1−x2)(1−x3)……1​
利用五边形数定理：

$f(x)=\frac{1}{1-x-x^2+x^5+x^7-x^{12}-x^{15}+...}$f(x)=1−x−x2+x5+x7−x12−x15+...1​

$f(x)=p_0+p_1x^1+p_2x^2+...+p_nx^n=\frac{1}{1-x-x^2+x^5+x^7-x^{12}-x^{15}+...}$f(x)=p0​+p1​x1+p2​x2+...+pn​xn=1−x−x2+x5+x7−x12−x15+...1​

$(p_0+p_1x^1+p_2x^2+...+p_nx^n)(1-x-x^2+x^5+x^7-x^{12}-x^{15}+...)=1$(p0​+p1​x1+p2​x2+...+pn​xn)(1−x−x2+x5+x7−x12−x15+...)=1

显然$p_0=1$p0​=1，所以除了常数项以外，每个项的系数都为零。

$p_nx^n-p_{n-1}x^{n-1}x-p_{n-2}x^{n-2}x^2+p_{n-5}x^{n-5}x^5+p_{n-7}x^{n-7}x^7-p_{n-12}x^{12}-p_{n-15}x^{15}+...=0$pn​xn−pn−1​xn−1x−pn−2​xn−2x2+pn−5​xn−5x5+pn−7​xn−7x7−pn−12​x12−pn−15​x15+...=0

$p_n-p_{n-1}-p_{n-2}+p_{n-5}+p_{n-7}-p_{n-12}-p_{n-15}+...=0$pn​−pn−1​−pn−2​+pn−5​+pn−7​−pn−12​−pn−15​+...=0

$p_n=p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+p_{n-12}+p_{n-15}-...$pn​=pn−1​+pn−2​−pn−5​−pn−7​+pn−12​+pn−15​−...

由五边形数定理得，n所减去的数列1,2,5,7,12,15,…可表达为$\frac{3k^2±k}{2}$23k2±k​

代码：