题意是模拟一个循环，一开始有一个空序列，之后每次循环：

1.从1到m中随机选出一个数字添加进去，每个数字被选的概率相同。

2.检查这个序列的gcd是否为1，如果为1则停止，若否则重复1操作直至gcd为1为止。

求这个序列的长度期望。

 

也是花了一晚上学习了一下期望dp。

 

设dp[i]表示当前gcd为i，到gcd为1时添加的元素个数期望。

然后就是传统的期望dp模型了：

 

dp[i]=∑p[i→j]dp[j]+w[i→j]

 

此处w为1，因为每次是添加1个元素

初始化状态dp[1]=0，因为当gcd为1的时候已经无法再添加元素

状态转移就是枚举i的因数j，然后计算1到m中有多少个数字x使得gcd(x,i)=j，设个数为tp，另一方面，还要计算有多少个数字y使得gcd(y,i)=i，设个数为z，从而有：

z=m/i（此处除法为向下取整）

dp[i]=z/m*dp[i]+Σ(tp/m*dp[j])+1 （此处的除法为取模意义下的除法，即乘以逆元）

也就是

dp[i]=(Σ(tp/m*dp[j])+1)*m/(m-z) （除法意义同上）

最后，由于起点并未明确确定，此处要手动设定起点，对于每个起点，都有1/m的概率选到，所以答案就是

1+Σdp[i]/m （取模下除法）

 

至于求tp，就是对x/i这个数字质因数分解之后容斥定理求个数，由于本人手残这部分写挂了好几次，终于也是在千辛万苦之后才写对

 

1 #include
      
         2 using namespace std;  3 #define ll long long  4 const ll mod=1e9+7;  5 ll q_p(ll a,ll b)  6 {  7     ll ans=1;  8     while(b)  9     { 10         if(b&1) 11         { 12             ans*=a; 13             ans%=mod; 14         } 15         b>>=1; 16         a*=a; 17         a%=mod; 18     } 19     return ans; 20 } 21 ll inv(ll x) 22 { 23     return q_p(x,mod-2); 24 } 25  26 ll ret; 27 vector
       
        vec; 28 void dfs(ll idx,ll dep,ll lim,ll num,ll tmp) 29 { 30     if(num>100000) return; 31     if(dep==lim) 32     { 33         if(lim%2) 34             ret+=tmp/num; 35         else 36             ret-=tmp/num; 37         return; 38     } 39     if(idx>=vec.size()) return; 40     dfs(idx+1,dep+1,lim,num*vec[idx],tmp); 41     dfs(idx+1,dep,lim,num,tmp); 42 } 43  44 bool vis[100005]; 45 ll calc(ll x,ll k,ll n) 46 { 47     ll tmp=n/k; 48     ll tt=x/k; 49     for(ll i=2;;i++) 50     { 51         while(tt%i==0) 52         { 53             if(!vis[i]) vec.push_back(i),vis[i]=1; 54             tt/=i; 55         } 56         if(i>sqrt(tt)) i=tt-1; 57         if(tt==1) break; 58     } 59     ret=0; 60     for(int i=1;i<=vec.size();i++) 61         dfs(0,0,i,1,tmp); 62     for(int i=0;i
        
         >m; 77     dp[1]=0; 78     ll invm=inv(m); 79     for(ll i=2;i<=m;i++) 80     { 81         dp[i]=1; 82         for(ll j=1;j<=sqrt(i);j++) 83         { 84             if(i%j==0) 85             { 86                 //cout<
         <<" "<
          
           <<" "<
           
            <<" "<
           
          
        
       
      

 

 

是不是写的很烂，写的很烂就对了

别人构造级数求和一下就过了，本蒟蒻还在搞期望dp，顶不住鸭。