Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P5589 【小猪佩奇玩游戏】

posted on 2019-10-16 17:21:28 | under 题解 |

这题还是比较妙妙套路的,复杂度为 $O(log^2N)$ ,可以卡掉 $\sqrt n$ 的做法

首先我们可以把原数列分成很多个集合,集合之间肯定是两两独立的,考虑分别计算答案

我们定义 $f_i$ 为集合大小为i出现过多少次(集合大小最多为 $logN$ 级别), $g_i$ 表示集合大小为i删除完的期望步数

那么答案是可以表示成 $\sum_{i=1}^{log_N}{f_i*g_i}$

现在考虑怎么求出 $f_i, g_i$

你可能会好奇题目下方的提示有什么用,没错他就是给你求 $f_i$ 用的

考虑集合大小至少为i出现了多少次,记之为 $p_i$ ,那么 $p_k=n^{\frac{1}{k}}$

再考虑容斥,因为这个集合是有序集合,集合大小为 $a$ 的集合出现在集合大小为 $b$ 的集合中出现了 $\frac{b}{a}$ 次

证明:假设一个集合开始元素是 $x$ ,那么 $x^{a*k}≤x^{b}$ ,即 $a*k≤b$ ,即 $k ≤ \frac{b}{a}$

由于f集合大小不大,我们暴力算就行了,这里复杂度为 $O(log^2N)$ (可能可以套一个整除分块优化至 $O(logN*log \sqrt N)$ ,不太清楚怎么做)

然后考虑怎么就 $g_i$ (打表!)

对于每一个集合,我们只取他们的对数,于是问题就转化成给定一个排列,每次可以删除一个数及其倍数,求期望删除次数

发现对于每一个数,假设他的约数个数为 $d_i$ ,那么他是可能被 $d_i$ 个数删除的

考虑递推求出 $g_i$ ,那么 $g_i=g_{i-1}+\frac{1}{d_i}$ (一个数会被 $d_i$ 个数删完,只有 $\frac{1}{d_i}$ 的概率需要多花费一次来删掉这个新加入的数)

那么我们就做完了,总体复杂度为 $O(log^2N)$

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = s; i <= t; ++ i)
#define drep(i, s, t) for(int i = t; i >= s; -- i)
#define maxn 100005
int p[maxn], f[maxn], n, m;
double g[maxn], ans;
bool check(int a, int b, int n) {
    long long pax = a;
    for(; b; b --, pax = pax * a) if(pax > 1ll * n) return 1;
    return 0;
}
int get(int i, int n) {
    int l = 1, r = n, ans = n;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid, i, n)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    return ans - check(ans, i, n);
}
int d(int x) {
    int ans = 1;
    rep(i, 2, 30) {
        if(x % i) continue;
        int tot = 0;
        while(x % i == 0) ++ tot, x /= i;
        ans *= (tot + 1);
    }
    return ans;
}
void init() {
    g[1] = 1.0;
    rep(i, 2, 30) g[i] = g[i - 1] + 1.0 / d(i);
}
int main() {
    init(), scanf("%d", &m);
    while(m --) {
        scanf("%d", &n), ans = 1, p[31] = 1;
        rep(i, 1, 30) p[i] = get(i, n);
        rep(i, 1, 30) f[i] = p[i] - p[i + 1];
        drep(i, 1, 30) rep(j, 2, 30) f[i / j] -= f[i];
        rep(i, 1, 30) ans += g[i] * f[i];
        printf("%.10lf\n", ans);
    }
    return 0;
}