首页 > 其他分享 >CodeForces - 1139D

CodeForces - 1139D

时间:2024-07-19 20:07:01浏览次数:14  
标签:lfloor frac gcd limits sum CodeForces rfloor 1139D

题目大意

序列每次随机添加一个 \([1,m]\) 的整数,直到序列 \(gcd=1\) 停止,求期望操作次数。

分析

模拟过程发现只关心整个序列的 \(gcd\) 与下一次会添加什么,那么根据期望 \(dp\) 套路可得状态 \(f_{i}\) 表示当前序列 \(gcd=i\),期望还操作多少次使得 \(gcd=1\)。
考虑枚举下一个数,转移方程有:

\[f_{i}=1+\frac{1}{m}\sum\limits_{k=1}^mf_{gcd(i,k)} \]

解方程得:$$f_{i}=\frac{m+\sum\limits_{k=1,k\neq i}^mf_{gcd(i,k)}}{m-\lfloor\frac{m}{i}\rfloor}$$
看到有 gcd 形式,考虑莫比乌斯反演。

\[\sum\limits_{k=1,k\neq i}^mf_{gcd(i,k)}=\sum\limits_{d|i}f_d\sum\limits_{j=1}^m [gcd(i,j)=d] \]

反演得:

\[\sum\limits_{j=1}^m [gcd(i,j)=d]=\sum\limits_{x|\lfloor\frac{i}{d}\rfloor}\mu(x)\lfloor\frac{\lfloor\frac{m}{x}\rfloor}{d}\rfloor \]

答案为 \(1+\frac{1}{m}\sum\limits_{i=1}^m f_i\)。
时间复杂度近似 \(O(n\sqrt{n})\)

代码

int m,invm,f[N],mu[N],vis[N],inv[N];

vector <int> fac[N],prime;

void init(int n){
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j+=i)
			fac[j].pb(i);
	mu[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) mu[i]=mod-1,prime.pb(i);
		for(int j=0;prime[j]<=n/i;j++){
			vis[i*prime[j]]=1,mu[i*prime[j]]=(i%prime[j]==0?0:mod-mu[i]);
			if(i%prime[j]==0) break;
		}
	}
	inv[1]=inv[0]=1;
	for(int i=2;i<=n;i++)
		inv[i]=mod-(mod/i)*inv[mod%i]%mod;
}

void Main(){
	f[1]=0,m=rd;
	for(int i=2;i<=m;i++){
		for(int d:fac[i]){
			if(d==i) break;
			int sum=0;
			for(int x:fac[i/d])
				sum=(sum+mu[x]*(m/x/d)%mod)%mod;
			f[i]=(f[i]+sum*f[d]%mod)%mod;
		}
		f[i]=(f[i]+m)%mod*inv[m-m/i]%mod;
	}
	int ans=0;
	for(int i=1;i<=m;i++)
		ans=(ans+f[i])%mod;
	ans=(ans*inv[m]%mod+1)%mod;
	cout<<ans<<endl;
}

signed main(){
	init(N-10);
	int T=1;//rd;
	while(T--) Main();
}

标签:lfloor,frac,gcd,limits,sum,CodeForces,rfloor,1139D
From: https://www.cnblogs.com/smilemask/p/18312295

相关文章

  • Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
    A直接速通就好了,我第一眼看的时候以为是整个数组可以有重复的数字,后面发现是保证没有的,所以直接随便交换一下位置就结束了。B,很经典的CF题,随便推导一下就能够发现,如果我想要一个位置能够发生变化,那么唯一的要求就是他以及他前面的位置有1出现过。而且完全不需要考虑为了一个数字......
  • CF1139D
    https://www.luogu.com.cn/problem/CF1139D(暂时没有解释,咕咕咕~~~)最重要的部分是对式子的化简,令\(X\)为步数:\[\begin{align}E[X]&=\sum_jjP(X=j)\\&=\sum_j\sum_i^j1P(X=j)\\&=\sum_i\sum_{j\geqi}P(X=j)\\&=\sum_iP(X\geqi)\\&=1+\sum......
  • Educational Codeforces Round 139 (Rated for Div. 2)
    A.ExtremelyRound----------------------------------题解-------------------------------------因为数据范围只有1e6,我们只需要预处理出来1-1e6每个每个数包含多少个极圆整数就行了,然后t次查询就可以。这种预处理查询是面对多次询问时应该首先想到的。点击查看代码#incl......
  • CodeForces Round 898 (div 4) H题解析
     CodeForcesRound898(div4)H.Mad City                           大致思路   对于有n条边和n个点,说明这个图里面只有一个环并且两人同时开始和结束移动,所以可以得到当Valeriu进入到这个图里面的唯一......
  • Codeforces Round 958 (Div. 2)
    题目链接:CodeforcesRound958(Div.2)总结:C因为常数没转\(longlong\)\(wa\)两发,难绷。A.SplittheMultisetfag:模拟Description:给定一个\(n\)和一个\(k\),每次可以将\(n\)减掉一个数\(u\),然后插入\(x\)个数,\(x<=k\),并且插入的数之和等于\(u\)。求将其转化为全\(1\)的最......
  • Codeforces Round 957 (Div. 3)
    知识点1.几个数相乘时,更小的数增加会比更大的数增加得到的乘积来得大题解A.OnlyPluses1.几个数相乘时,当更小的数增大时,得到的乘积会比更大的数增大来得大,也就是更小的数字权重会比较大,那么在5次+1的过程中,每次找最小值++即可#include<bits/stdc++.h>#defineintlonglon......
  • Codeforces Round 898 (Div. 4)(A~H)
    目录A.ShortSortB.GoodKidC.TargetPracticeD.1DEraserE.BuildinganAquariumF.MoneyTreesG.ABBCorBACBH.MadCityA.ShortSortProblem-A-Codeforces暴力枚举每个位置的交换即可。#include<iostream>#include<algorithm>#include<queue......
  • Codeforces Round 957 (Div. 3)
    题目链接:CodeforcesRound957(Div.3)总结:E不懂,F差一个set去重A.OnlyPlusesfag:枚举B.AngryMonkfag:模拟Solution:分裂的花费为\(a_i-1\),添加的花费为\(a_i\)。C.GorillaandPermutationfag:思维Solution:大于等于\(k\)的数,逆序放在最前面,小于等于\(m\)的数,从最后面......
  • Codeforces Round 958 (Div. 2)补题
    文章目录A题(拆分多集)B题(获得多数票)C题(固定OR的递增序列)A题(拆分多集) 本题在赛时卡的时间比较久,把这题想复杂了,导致WA了两次。后来看明白之后就是将n每次转换成k-1个1,到最后分不出来k-1个1直接一次就能分完,即结果加一;#include<bits/stdc++.h>#definein......
  • CodeForces 1983A Array Divisibility
    题目链接:CodeForces1983A【ArrayDivisibility】思路    按规律可得,当a[i]=i时满足题目要求。代码#include<functional>#include<iostream>#include<algorithm>#include<queue>#include<stdio.h>#include<string>#include<cstring......