整数拆分

(6 mins to read)

不能相等

将正整数n划分成不能相等的若干个正整数的和的方案数由于不能相等,所以划分成的数字个数不超过$\sqrt n$​设$f_{i,j}$​表示将i划分成j个不同数字的和的方案数$f_{i,j} = f_{i-j,j} + f_{i-j,j-1}$​$O(n\sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, B = 350, mod = 1e9 + 7;
int n, f[N][B];
inline int add(int x, int y) { return (x+y>=mod) ? x+y-mod : x+y; }
int main()
{
scanf("%d", &n);
f[0][0] = 1;
for(int i=1; i<=n; i++)
for(int j=1; j<=i && j<B; j++)
f[i][j] = add(f[i-j][j], f[i-j][j-1]);
int ans = 0;
for(int j=1; j<B; j++) ans = add(ans, f[n][j]);
printf("%d\n", ans);
return 0;
}

能相等

将正整数n划分成若干正整数的和的方案数设定阈值$B=\sqrt n$对于<B的部分,直接做完全背包对于>=B的部分,选择的数字个数不超过B设$f_{i,j}$​表示将i划分成j个不同数字的和的方案数$f_{i,j} = f_{i-B,j-1} + f_{i-j,j}$$O(n\sqrt n)O$ 但只能解决单次询问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, B = 350, mod = 1e9 + 7;
int n, f0[N], f1[N], f[N][B];
inline int Mul(int a, int b) { return 1ll*a*b%mod; }
inline void add(int &a, int b) { a+=b; if(a>=mod) a-=mod; }
inline int Add(int a, int b) { return (a+b>=mod) ? a+b-mod : a+b; }
int main()
{
scanf("%d", &n);
f0[0] = f1[0] = 1;
for(int j=1; j<B && j<=n; j++)
for(int i=j; i<=n; i++)
f0[i] = Add(f0[i], f0[i-j]);
f[0][0] = 1;
for(int i=B; i<=n; i++)
for(int j=1; j<=B; j++)
{
f[i][j] = Add(f[i-B][j-1], f[i-j][j]);
f1[i] = Add(f1[i], f[i][j]);
}
int ans = 0;
for(int i=0; i<=n; i++) add(ans, Mul(f0[i], f1[n-i]));
printf("%d\n", ans);
return 0;
}

五边形数$\frac{n(3n-1)}{2}$欧拉函数$\phi(n) = \prod \limits_{i=1}^{\infty}(1-x^i) = \prod\limits_{i=-\infty}^{\infty}(-1)^ix^{\frac{i(3i-1)}{2}}$​即展开后只留下幂次为广义五边形数的项考虑整数拆分的生成函数$F(x) = \sum\limits_{i=1}^{\infty} P(i)x^i =\prod \limits_{i=1}^{\infty}(1+x^i+x^{2i}…)= \prod\limits_{i=1}^{\infty}\frac{1}{1-x^i}$​即$F(x)\phi(x)=1$可以得到$P(n)-P(n-1)-P(n-2)+P(n-5)+P(n-7)-…=0$容易发现P(n)可由$n-\dfrac{i(3*i-1)}{2}$​以及$n-\dfrac{i(3*i+1)}{2}$​更新得到由于五边形数是$n^2$级别增长的,所以可以$O(n\sqrt n)$递推得到$P(1)\dots P(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, B = 350, mod = 1e9 + 7;
int n, m, i, j, f[B], g[N];
int main()
{
scanf("%d", &n);
for(f[1]=1,f[2]=2,f[3]=5,f[4]=7,i=5; f[i-1]<n; i++) f[i] = 3 + 2*f[i-2] - f[i-4];
for(g[0]=i=1; i<=n; i++)
for(j=1; f[j]<=i; j++)
if((j+1)>>1&1) g[i] = (g[i] + g[i-f[j]])%mod;
else g[i] = (g[i]-g[i-f[j]]+mod)%mod;
printf("%d\n", (g[n]<0) ? g[n]+mod : g[n]);
return 0;
}

沈阳的I题是询问n个点深度不超过2的树的个数,显然是个n-1的整数拆分,然而$n \leq 5\times10^5$

  1. $O(n\sqrt n)$取模优化,g数组开成longlong,这样对于$g_i$​只要在最后取一次模即可,因为最多根号次加法所以不会爆longlongcachemiss优化,$g_i$​用变量x代替,这样可以一定程度上减少cache的miss循环优化,大力循环展开然后就能过了

  2. $O(n\log n)$更快也更简单,只需要对$\phi$求个逆即可