[LibreOJ 2803][CCC2018]平衡树
转载请注明出处：http://danihao123.is-programmer.com/
假设每个结点都有正整数权值，那么我们定义完美平衡树：权值为\(1\)的单点树是完美平衡树；根的权值为\(w(w\geq 2)\)的话，那么它一定有\(k(2\leq k\leq w)\)个子树，每个子树要完全一致，并且每个子树的根权值都要是\(\lfloor\frac{w}{k}\rfloor\)。
给定\(N\)，计算根权值为\(N\)的完美平衡树的数量。
\(1\leq N\leq 10^9\)。
我只会做水题力……
假设\(f(n)\)为根权值为\(n\)的完美平衡树数量，那么显然有\(f(n) = \sum_{i = 2}^n f(\lfloor\frac{n}{i}\rfloor)\)，那么直接用类似于DP的做法的话那么一次转移的复杂度为\(O(\sqrt{n})\)，而所有状态一定可以由\(n\)整除一个正整数得到，那么这个东西的复杂度就和没预处理的杜教筛一样了……
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <utility>
using ll = long long;
std::unordered_map<int, ll> d;
ll dp(int n) {
if(n == 1) return 1;
if(d.count(n)) return d[n];
ll ans = 0;
for(int i = 2; i <= n;) {
int next = n / (n / i);
ans += (ll(next - i + 1)) * dp(n / i);
i = next + 1;
}
d[n] = ans;
#ifdef LOCAL
printf("d[%d] : %lld\n", n, ans);
#endif
return ans;
}
int main() {
int n; scanf("%d", &n);
// puts("Gou!");
printf("%lld\n", dp(n));
return 0;
}
Sep 19, 2022 01:03:34 AM
Mathematics is one of the tough subjects and also an easy subject for class 10th standard students of TM, EM, AP SSC Maths Model Paper UM and HM studying at government and private schools of the state. Department of School Education and teaching staff of various institutions have designed and suggested the Mathematics question paper with solutions for all chapters topic wide for each lesson of the course, and the AP SSC Maths Model Paper 2023 Pdf designed based on the new revised syllabus and curriculum.