Codeforces 1139D（期望dp）

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

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这个数字质因数分解之后容斥定理求个数，由于本人手残这部分写挂了好几次，终于也是在千辛万苦之后才写对

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const ll mod=1e9+;

 ll q_p(ll a,ll b)

 {

     ll ans=;

     while(b)

     {

         if(b&)

         {

             ans*=a;

             ans%=mod;

         }

         b>>=;

         a*=a;

         a%=mod;

     }

     return ans;

 }

 ll inv(ll x)

 {

     return q_p(x,mod-);

 }

 ll ret;

 vector<ll>vec;

 void dfs(ll idx,ll dep,ll lim,ll num,ll tmp)

 {

     if(num>) return;

     if(dep==lim)

     {

         if(lim%)

             ret+=tmp/num;

         else

             ret-=tmp/num;

         return;

     }

     if(idx>=vec.size()) return;

     dfs(idx+,dep+,lim,num*vec[idx],tmp);

     dfs(idx+,dep,lim,num,tmp);

 }

 bool vis[];

 ll calc(ll x,ll k,ll n)

 {

     ll tmp=n/k;

     ll tt=x/k;

     for(ll i=;;i++)

     {

         while(tt%i==)

         {

             if(!vis[i]) vec.push_back(i),vis[i]=;

             tt/=i;

         }

         if(i>sqrt(tt)) i=tt-;

         if(tt==) break;

     }

     ret=;

     for(int i=;i<=vec.size();i++)

         dfs(,,i,,tmp);

     for(int i=;i<vec.size();i++) vis[vec[i]]=;

     vec.clear();

     return tmp-ret;

 }

 ll dp[];

 int main()

 {

     #ifdef amori

     clock_t start = clock();

     #endif //amori

     ll m;

     cin>>m;

     dp[]=;

     ll invm=inv(m);

     for(ll i=;i<=m;i++)

     {

         dp[i]=;

         for(ll j=;j<=sqrt(i);j++)

         {

             if(i%j==)

             {

                 //cout<<i<<" "<<j<<" "<<calc(i,j,m)<<" "<<calc(i,i/j,m)<<endl;

                 dp[i]+=dp[j]*invm%mod*calc(i,j,m);

                 dp[i]%=mod;

                 if(j!= && i!=j*j)

                 {

                     dp[i]+=dp[i/j]*invm%mod*calc(i,i/j,m);

                     dp[i]%=mod;

                 }

             }

         }

         ll tp=m/i;

         dp[i]=dp[i]*m%mod*inv(m-tp);

         dp[i]%=mod;

     }

     ll sum=;

     for(int i=;i<=m;i++)

     {

         sum+=dp[i];

         sum%=mod;

     }

     cout<<sum*invm%mod+<<endl;

     #ifdef amori

     clock_t end = clock();

     cout<<"Done in "<<end-start<<"ms"<<endl;

     #endif // amori

 }

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

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

巴特西

Codeforces 1139D（期望dp）

最新文章

热门文章