[LibreOJ 2803][CCC2018]平衡树

danihao123 posted @ 2018年9月07日 13:08 in 题解 with tags loj CCC 杜教筛 , 51 阅读
转载请注明出处: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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter