P5589 【小猪佩奇玩游戏】

这题还是比较妙妙套路的，复杂度为\(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;

}

巴特西

P5589 【小猪佩奇玩游戏】

\(Code:\)

最新文章

热门文章