并不对劲的P5589

题目大意

有\(n\)(\(n\leq 10^9\))个数：\(1,2,...,n\)，每次操作是随机取一个没被删除的数\(x\)，并删去\(x,x^2,x^3,...\)。

求期望几次删完所有数。

题解

可以把问题转换成：有\(n\)个数，每次操作随机取一个数\(x\)，若\(x\)未被标记则标记\(x,x^2,x^3,...\)并删去\(x\)，反之则删去\(x\)，求期望删多少个未被标记的数。

发现一个数\(x\)被计入答案的充要条件是\(\forall y\in\{1,2,3,...,n\}\)满足\(\exists k,y^k=x\)，删除序列中\(y\)在\(x\)之后。

记\(y\)的个数为\(p\)，问题变成有\(p+1\)个数的排列，指定的数在第一个的概率。这个问题的答案是\(\frac{1}{p+1}\)。

也就是说，设\(p_i\)表示当\(x=i\)时\(y\)的个数，那么原问题的答案是\(\sum\limits_{i=1}^n \frac{1}{p_i+1}\)。

这个式子看上去只能\(\Theta(n)\)地求。

发现\([2,n]\)中有\(\lfloor \sqrt n \rfloor-1\)个平方数，三次根号\(n\)下取整减1个立方数……，\(p_i\neq 0\)的数的个数很少，这些数可以暴力求。

\(p_i=0\)的数的\(\frac{1}{p_i+1}=1\)，可以直接求。

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];~k;k=nxt[k])

#define LL long long

#define maxn 1000007

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(int x)

{

    if(x==0){putchar('0'),putchar('\n');return;}

    int f=0;char ch[20];

    if(x<0)putchar('-'),x=-x;

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');

    return;

}

int n,t,mx=1e9,pos[maxn],cnt;

map<int,int>mp;

LL mul(LL x,int y){LL res=1;while(y){if(y&1)res*=x;x*=x,y>>=1;}return res;}

int main()

{

	rep(i,2,30)

	{

		LL now=mul(2,i);int j;

		for(j=2;now<=mx;)

		{

			mp[now]++;

			if(mp[now]==1)pos[++cnt]=now;

			j++;now=mul(j,i);

		}

	}

	t=read();

	while(t--)

	{

		n=read();

		double ans=0.0;int num=0;

		rep(i,1,cnt)if(pos[i]<=n)num++,ans+=1.0/((double)(mp[pos[i]]+1));

		ans+=(double)(n-num);

		printf("%.8lf\n",ans);

	}

	return 0;

}

一些感想

伟大的ysf口胡的

巴特西

并不对劲的P5589

题目大意

题解

代码

一些感想

最新文章

热门文章