题解 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; } ```