不能相等
将正整数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$
-
$O(n\sqrt n)$取模优化,g数组开成longlong,这样对于$g_i$只要在最后取一次模即可,因为最多根号次加法所以不会爆longlongcachemiss优化,$g_i$用变量x代替,这样可以一定程度上减少cache的miss循环优化,大力循环展开然后就能过了
-
$O(n\log n)$更快也更简单,只需要对$\phi$求个逆即可