题解 P4808 【[CCC 2018]平衡树】

· · 题解

可以列出如下递归式 :

f_x = \sum_{k = 2}^{n} f(\lfloor \frac{x}{k} \rfloor) \quad \quad x >1 f_1 = 1

对于 k \in [2, n] 的 \lfloor \frac{n}{k} \rfloor 可以使用整除分块的套路来统计。整除分块中, 对于 \lfloor \frac{N}{i} \rfloor , 使 \lfloor \frac{N}{i'} \rfloor 等于它的最大的 i' 为 \lfloor \frac{N}{\lfloor \frac{N}{i} \rfloor} \rfloor。
技巧 : 把整除分块的结果映射到连续数列上。设结果为 x 。对于 x \leqslant \sqrt N 的结果显然是连续的, 映射到 x 本身。对于 x > \sqrt N 的结果显然有 \frac{N}{x} < \sqrt N。映射到 \sqrt N + x 。
状态数 \mathcal{O(\sqrt N)} 。记忆化搜索一下就好了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 400010;
ll f[M]; 
int n, sqn;
inline int toId(int x) {
    return x <= sqn ? x : n / x + sqn;
}

ll solve(int n) {
    int fid = toId(n);
    if(~f[fid]) return f[fid];
    if(n == 1) return 1;
    ll ans = 0;
    int r = 0;
    for(int k = 2; k <= n; k = r + 1) {
        r = n / (n / k);
        ans += r >= k ? (r - k + 1) * solve(n / k) : 0;
    }
    return f[fid] = ans;
}

int main() {
    memset(f, -1, sizeof(f));
    cin >> n;
    sqn = sqrt(n);
    cout <<solve(n) << endl;
    return 0;
}