PerfectPan
;

Codeforces 1139D Steps to One

March 23, 2019

题目链接https://codeforces.com/contest/1139/problem/D

题意:有一个数组刚开始为空,每次等概率随机一个 [1,m][1,m] 的数字加入到数组末尾,当整个数组 gcdgcd11 时停止加入,问期望步长。

思路:定义 dp[x]dp[x] 为整个数组 gcdgcdxx 时期望停止的步长,则由全期望公式得转移方程为:

dp[x]=1+i=1mdp[gcd(i,x)]mdp[x]=1+\sum_{i=1}^{m}\frac{dp[gcd(i,x)]}{m}

我们把 gcd(i,x)==xgcd(i,x)==x 的项移到左边就可以在 O(m2)O(m^2) 的时间内暴力解出,但这无疑会超时,考虑到 gcd(i,x)gcd(i,x) 一定是 xx 的约数,所以我们可以枚举 xx 的约数 yy 同时计算出 i=1m[gcd(i,x)==y]\sum_{i=1}^{m}[gcd(i,x)==y] 的个数,这是一个经典的反演式子,可以加速计算,最后求出所有 dpdp 值以后,考虑第一步数组为空,所以由全期望公式就可以得出答案为:

1+i=1mdp[i]m1+\sum_{i=1}^{m}\frac{dp[i]}{m}
#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
const int P=1e9+7;
int m,i,j,inv,ans=1,dp[N],mu[N],primes[N];
vector<int>fac[N];
void init(){
    for (mu[1]=1,i=2;i<=1e5;i++){
        if (!primes[i]) primes[++primes[0]]=i,mu[i]=-1;
        for (j=1;j<=primes[0]&&i*primes[j]<=1e5;j++){
            primes[i*primes[j]]=1;
            if (i%primes[j]==0){
                mu[i*primes[j]]=0;
                break;
            }
            else mu[i*primes[j]]=-mu[i];
        }
    }
    for (i=1;i<=1e5;++i){
    	for (j=i*2;j<=1e5;j+=i){
    		fac[j].PB(i);
    	}
    }
}
int fexp(int a,int n){
	int res=1;
	while (n){
		if (n&1) res=1LL*res*a%P;
		a=1LL*a*a%P;
		n>>=1;
	}
	return res;
}
inline void up(int&a,int b){a+=b;if(a>=P)a-=P;}
int totCount(int y,int x){
	int cnt=0;
	x/=y;
	for (int i=0;i<(int)fac[x].size();++i){
		int d=fac[x][i];
		int res=mu[d]*(m/y/d);
		if (res<0) res+=P;
		up(cnt,res);
	}
	int res=mu[x]*(m/y/x);
	if (res<0) res+=P;
	up(cnt,res);
	return cnt;
}
int main(){
	init();
	inv=fexp(read(m),P-2);
	for (dp[1]=0,i=2;i<=m;++i){
		int res=1;
		for (j=0;j<(int)fac[i].size();++j){
			int cnt=totCount(fac[i][j],i);
			up(res,1LL*dp[fac[i][j]]*cnt%P*inv%P);
		}
		dp[i]=1LL*res*m%P*fexp(m-m/i,P-2)%P;
		up(ans,1LL*dp[i]*inv%P);
	}
	printf("%d\n",ans);
	return 0;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.