Codeforces #548 Div2 D. Steps to One

この回も割と速く解けたね。
https://codeforces.com/contest/1139/problem/D

問題

整数Mが与えられる。
初期状態で空の整数列Aがある。
ここに、1～Mのいずれかを等確率で1個ずつ追加していくものとする。
全体のGCDが1になった段階で終了するとしたとき、整数列の長さの期待値はいくつか。

解法

f(x):=既存のGCDがxの時、GCDが1になるまであと何要素追加されるかという期待値
とする。求めたいのは1+avg(f(1)+f(2)+f(3)+...+f(M))なので、結局f(1)～f(M)を求めればよい。

GCDがxの時、1要素追加してGCDが遷移する先はxの約数なので、包除原理の要領で、1～Mが出たときGCDが各約数になるケースを数え上げていけばよい。

int M;
ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll dp[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	for(i=2;i<=M;i++) {
		vector<int> C;
		for(j=1;j*j<=i;j++) if(i%j==0) {
			C.push_back(j);
			if(j*j!=i) C.push_back(i/j);
		}
		sort(ALL(C));
		vector<int> num(C.size());
		for(j=C.size()-1;j>=0;j--) {
			num[j]=M/C[j];
			for(x=j+1;x<C.size();x++) if(C[x]%C[j]==0) num[j]-=num[x];
		}
		dp[i]=M;
		FOR(j,C.size()-1) (dp[i]+=dp[C[j]]*num[j])%=mo;
		dp[i]=dp[i]*modpow(M-num.back())%mo;
	}
	ll ret=0;
	for(i=1;i<=M;i++) (ret+=dp[i])%=mo;
	ret=(1+ret*modpow(M))%mo;
	cout<<ret<<endl;
}

まとめ

この回はDから正答数少ないな。