题解 P5589 【小猪佩奇玩游戏】
本文最后更新于 766 天前,内容如有失效请评论区留言。

推荐原文阅读

$\Theta(T\log^2 n)$的解法,搞了我半个下午才弄出来

蒟蒻的我反复看了几遍视频讲解,并经过反复推敲,终于弄懂了$\log^2$的做法

以下题解主要是对$memset0$巨佬题解的补充说明,尤其是高能部分,这里重点讲解具体如何计算大小为$i$的集合个数,至于计算删除大小为$i$的集合的期望次数可以见其它题解,已经讲的很清楚了

  • $\sqrt n$的做法,复杂度的瓶颈在于计算有多少个大小为$i$的集合

  • 大小为$i$的集合应该是$\lfloor n^{\frac{1}{i} }\rfloor$个,考虑集合中最小的数字$x$,那么$x^i \le n$, 则$x \le \lfloor n^{\frac{1}{i} }\rfloor$

  • 由于$1^{\text{任意次方}} = 1$, 所以$1$提出来单独计算,故上面计算出的个数还要再$-1 $

  • 表示我们可以把$2 \sim x$的数作为那些集合的首项(集合中最小的元素), 例如$i = 2, x = 4$, 那么集合就有$\text{{2, 4}, {3, 9}, {4, 16}}$

  • 但是我们发现,其实像${2, 4}, {4, 16}$的集合不一定是极大的,它可能被包含在${2, 4, 8, 16}$这样的集合中

  • 不是极大的集合意味着它可以扩张到更大的集合,而且它不是独立的,与外部有连边

  • 为了去除那些不合法的集合(不是极大的集合), 问题转化为如何计算一个集合被更大的集合包含了多少次,我们要从答案中减掉这些不合法的贡献

  • 对于一个确定的集合$S$,该集合的大小为$a$, 最小元素为$x$, 设较小集合的大小为$b$, 在较大集合中出现了$k$次($k$即是我们想求的), 我们考虑较小集合的首项(较小集合中最小的元素) $y = x^k(y \in S)$, 例如$S = {2, 4, 8, 16}$,则$a = 4, x = 2$,当$b = 2$时,$y = 2, 4$

  • 可知较小集合的最大元素是$y^b$, 并且由于$y^b \in S$, 则

$$y^b \le x^a$$

$$x^{kb} \le x^a$$

$$kb \le a$$

$$k \le \lfloor \frac{a}{b} \rfloor$$

  • 不难发现$k$这个值只和两个集合的大小有关, 因此对于大小为$a$的较大集合, 设该集合有$tot$个,那么对于大小为$b(b < a)$的较小集合, 它会在大小为$a$的集合中出现$tot \times \lfloor \frac{a}{b} \rfloor$个,这些贡献是不合法的,应该减掉

  • 在实现程序中为了避免重复减掉同样的贡献,可以用倒序循环实现,具体见程序

  • 这题毒瘤卡精度,$pow$会因为精度$WA \ \ 1$个点,可以使用二分 $+ $快速幂代替$pow$函数

以下程序可以处理$n \le 10^{18}$的数据,$d[i]$表示$i$的约数个数(使用线性筛实现,只是为了复习下), $f[i]$和$g[i]$分别表示大小为$i$的集合的个数,和大小为$i$的集合的期望删除次数,其它数组是线性筛里面的

//ID: LRL52  Date: 2019.10.16
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#include<bits/stdc++.h>
using namespace std;
const int N = 1055, M = 2055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
    int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
    while(cc >= '0' && cc <= '9'){x = x * 10 + (cc ^ 48); cc = gc();} x *= f;
}
#define int long long
#define double long double
int Pcnt, n;
int d[75], vm[75], prime[75], vm2[75], f[75], h[75];
double g[75], Res;

void Prework(){
    d[1] = 1;
    rep(i, 2, 65){
        if(!vm[i]){
            vm[i] = vm2[i] = i, prime[++Pcnt] = i;
            d[i] = 2;
        }
        rep(j, 1, Pcnt){
            if(prime[j] > vm[i] || prime[j] > 65 / i) break;
            int x = i * prime[j];
            vm[x] = prime[j];
            if(i % prime[j]){
                vm2[x] = prime[j];
                d[x] = d[i] * d[prime[j]];
            }
            else{
                vm2[x] = vm2[i] * prime[j];
                if(x == vm2[x]) d[x] = d[i] + 1;
                else d[x] = d[x / vm2[x]] * d[vm2[x]];
            }
        }
    }
    g[1] = 1.0;
    rep(i, 2, 65) g[i] = g[i - 1] + 1.0 / d[i];
}

int qp(int a, int k){
    int ret = 1; double _a = a;
    Res = 1.0;
    while(k){
        if(k & 1) ret = ret * a, Res = Res * _a;
        a = a * a;
        _a = _a * _a;
        k >>= 1;
    }
    return ret;
}

int calc(int n, int k){
    int l = 1, r = n;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(qp(mid, k) > n || Res > 1e18) r = mid - 1;
        else l = mid + 1;
    }
    return r;
}

#undef int
int main(){
#define int long long
    Prework();
    int Task; rd(Task);
    while(Task--){
        rd(n);
        if(n == 0){
            puts("0.00000000");
            continue;
        }
        double ans = 1.0;
        int up = n;
        rep(i, 1, n){
            //h[i] = pow(n, 1.0 / i);
            h[i] = calc(n, i); //calc n^(1/i)
            --h[i];
            if(h[i] == 0){
                up = i - 1;
                break;
            }
        }
        for(int i = up; i >= 1; --i){
            f[i] = h[i];
            rep(j, i + 1, up)
                f[i] -= (j / i) * f[j];
        }
        rep(i, 1, up) ans += f[i] * g[i];
        printf("%.8Lf\n", ans);
    }
    return 0;
}

评论

  1. 1L5Y9G
    Windows Chrome 98.0.4758.102
    2 年前
    2022-3-06 11:52:14

    评论测试
    {{keai}}

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇