概率dp

1. Codeforces 1753C

题意：

给定一个0和1组成的数组，每次随机选择两个位置 $i$ 和 $j$ ，如果 $a[i]<a[j]$ ，那么交换 $a[i],a[j]$ ，问交换多少次可以使得数组变为不下降数组的期望值，答案对 $998244353$ 取模。

题解：

可以发现最终状态是 $000111$ 的形式，假设一共有 cnt 个0，那么这些 0 最终状态一定是位于数组的前面 cnt 个位置，那么我们可以找出初始状态在这前 cnt 个位置的1，求出把这些 1 交换到后面位置的期望值就是答案
取出两个位置的概率是 $C(n,2)$ ，在还有 $i$ 个 $1$ 还没归为的时候，取到对应 $(0,1)$ 的概率是 $pi=(i*i)/C(n,2)$ 。
$dp[i]=pi*dp[i-1]+(1-pi)*dp[i]+1$ ，化简得，单步期望步数为 $1/p$ 。
计算后把各个值相加就是答案，答案需要取模，所以要采用逆元。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
ll qpow(ll a,ll b){
    ll res=1%mod;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1,a=a*a%mod;
    }
    return res;
}
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n+1,0);
    int cnt=0,num1=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt+=(a[i]==0);
    }
    for(int i=1;i<=cnt;i++){
        num1+=(a[i]==1);
    }
    ll ans=0;
    for(int i=1;i<=num1;i++){
        ans=(ans+qpow(1ll*i*i%mod,mod-2))%mod;
    }
    cout<<1ll*n*(n-1)/2%mod*ans%mod<<endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

2. Codeforces 148D

Bag of mice

题意：

袋中有w只白鼠和b只黑鼠，王妃和龙轮流从袋中抓取，谁先抓到白鼠谁胜。
王妃先抓,然后龙抓,龙抓完后会随机逃走一只老鼠。若袋中老鼠抓完但王妃和龙都没抓到白鼠，则龙获胜。
问王妃获胜的概率。

题解：

$dp[i][j]$ 表示袋中还剩 $i$ 只白鼠和 $j$ 只黑鼠的时候王妃获胜的概率。王妃获胜的必要条件是龙始终抓到黑鼠。
王妃抓到白鼠， $dp[i][j]+=i/(i+j)$ ;
王妃抓到黑鼠，龙抓完跑掉黑鼠， $dp[i][j]+=dp[i][j-3] * j/(i+j) * (j-1)/(i+j-1) * (j-2)/(i+j-2)$ ;
王妃抓到黑鼠，龙抓完跑掉白鼠， $dp[i][j]+=dp[i-1][j-2] * j/(i+j) * (j-1)/(i+j-1) * (i-1)/(i+j-2)$ ;

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<vector<double>>dp(n+1,vector<double>(m+1));
    for (int i = 1; i <= n; i++)dp[i][0] = 1;
    for (int i = 1; i <= m; i++)dp[0][i] = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){ 
            dp[i][j] +=(double)i/(i+j);
            if(j>=3)dp[i][j]+=(double)j/(i + j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];
            if(i>=1&&j>=2)dp[i][j]+=(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+ j-2)*dp[i-1][j-2];
        }
    }
    cout<<fixed<<setprecision(10)<<dp[n][m]<<'\n';

}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

3. Codeforces 626D

D. Jerry’s Protest

题意：

两个小孩玩游戏，游戏规则如下：有n个球，每个球有一个分数，每次这两个小孩从这n个球中等概率随机选取一个球并得到球的分数，谁的得分高谁赢，每局游戏结束后将球放回去。问现在A和B玩儿了三局游戏，A赢了前两局，B赢了第三局，B的得分比A的得分高的概率。

题解：

$p[i]$ 表示某局获胜并且差值为i的概率， $dp[i]$ 一二两局甲获胜并且差值为i的概率
那么可以对球的分数排序后，求出获胜的差值的概率，再求出前两个A胜的概率，再求出第三局胜利并且取胜的差值大于前两局A取得的分数差。
多个方案求和就行。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long

double dp[5010];  
double p[5010];  
int a[5010];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            p[a[i]-a[j]]+=1.0/(n*(n-1)/2);
        }
    }
    for(int i=1;i<=5000;i++){
        for(int j=1;j<=5000;j++){
            if(i+j<=5000)dp[i+j]+=p[i]*p[j];
        }
    }
    double ans=0;
    for(int i=1;i<=5000;i++){
        for(int j=1;j<i;j++){
            ans+=dp[j]*p[i];
        } 
    }
    cout<<fixed<<setprecision(10)<<ans<<'\n';

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

4. Codeforces 518D

D. Ilya and Escalator

题意：

n个人在电梯外等候，每隔一秒有p的概率有一人进入电梯。问t秒后电梯中的人数的期望。

题解：

$dp[i][j]$ 表示 $i$ 秒后电梯中有 $j$ 个人的概率
当电梯中没人时， $j==0, dp[i][j]+=dp[i-1]*(1-p)$
当人还没上完， $0<j<n,dp[i][j]+=dp[i-1][j-1]*p+dp[i-1][j]*(1-p)$
当人已经上满， $j==n,dp[i][j]+=dp[i-1][j-1]*p+dp[i-1][j]$
$ans=dp[t][1]*1+dp[t][2]*2+...dp[t][n]*n$

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2001;
double dp[N][N];
void solve()
{
    int n, t;
    double p;
    cin >> n >> p >> t;
    dp[0][0] = 1;
    for(int i = 1 ; i <= t ; i++){
        for(int j = 0 ; j <= n ; j++){
            dp[i][j] += (j == n ? dp[i-1][j] : dp[i-1][j]*(1-p));
            if(j-1 >= 0){
                dp[i][j] += dp[i-1][j-1]*p;
            }
        }
    }
    double ans = 0;
    for(int i = 1 ; i <= n ; i++){
        ans += dp[t][i]*i;
    }
    cout << fixed << setprecision(6) << ans << endl;

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

5. Codeforces 235B

B. Let’s Play Osu!

题意：

给出一段长为 $n$ 的字符串，只含 $O$ 和 $X$ ，第i个位置出现 $O$ 的概率为 $pi$ ,若字符串中出现连续 $k$ 个 $O$ ，则得分加上 $k^2$ ，问最终得分的期望。

题解

$dp[i]$ 表示前i个字符得分的期望
$2*C(n,2)+n=n^2$
$dp[i]=(dp[i-1]+p[i-1])p[i],ans=p[1]+p[1]+…+p[n] + 2(dp[2]+dp[3]+…dp[n])

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200005;
double dp[N], p[N];
void solve()
{
    int n;
    cin >> n;
    double ans = 0;
    for(int i = 1; i <= n; i++)
    {
        cin>>p[i];    
        ans += p[i];
    }
    for(int i = 1; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + p[i - 1]) * p[i];
        ans += 2 * dp[i];
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

6. Codeforces 167B

B. Wizards and Huge Prize

题意：

给定一个初始容量为 $k$ 的背包，你背上它去打 $n$ 场比赛，第 $i$ 场比赛获胜的概率为 $pi$ ，奖励为 $ai$ ,若 $ai=-1$ ，你可以获得体积为 $1$ 的奖品。若 $ai!=-1$ ，你可以将背包容量扩充 $ai$ 。问至少获胜 $l$ 场比赛并且将所有已得奖品带走的概率。

题解：

$dp[i][j][k]$ :打 $i$ 场比赛，获胜 $j$ 场，背包容量剩余k的概率
第 $i$ 场输： $dp[i][j-1][k]+=dp[i-1][j-1][k]*(1-pi)$ ;
第 $i$ 场赢： $dp[i][j][k+a[i]]+=dp[i-1][j-1][k]*pi$
因为可以按照一定的顺序进行打怪，那么我们可以把 $0$ 偏移 $200$ ，这样负数的情况就代表后来才处理的情况

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long

double dp[210][210][410];
void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    vector<double>p(n+1,0);
    vector<int>a(n+1,0); 
    for(int i=1;i<=n;i++){
        cin>>p[i];
        p[i]=p[i]/100;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[0][0][k+200]=1;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            for(int k=0;k<=400;k++){
                dp[i][j-1][k]+=dp[i-1][j-1][k]*(1-p[i]);
                int x=min(400,k+a[i]);
                if(x>=0){
                    dp[i][j][x]+=dp[i-1][j-1][k]*p[i];
                }
            }
        }
    }
    double ans=0.0;
    for(int i=m;i<=n;i++){
        for(int j=200;j<=400;j++)ans+=dp[n][i][j];
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

7. Codeforces 768D

D. Jon and Orbs

题意：

给定k种物品，每天会产生任意一种物品，每种物品产生概率相同。
q次询问，每次询问给定p，问产生k种物品并且概率不小于 $(p-10^-7)/2000$ 的最少天数.

题解：

每种产生的概率是 $1/k$
$dp[i]$ :产生i种物品的概率
$dp[i]=dp[i]*(i*p)+dp[i-1]*((k-i+1)*p)$ ;

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2000;
const double eps=1e-7;
double dp[N];

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int>ans(1010);
    int id=1;
    dp[0]=1;
    for(int i=1;id<=1000;i++){
        for(int j=n;j>0;j--)dp[j]=dp[j]*j/n+dp[j-1]*(n-j+1)/n;

        while(id<=1000&&dp[n]>=(id-eps)/2000){
            ans[id]=i;
            id++;
        }
        dp[0]=0;
    }

    while(m--){
        int q;
        cin>>q;
        cout<<ans[q]<<'\n';
    }

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

8. Codeforces 540D

题意：

指定r个人出石头，s个人出剪刀，p个人出布。
每隔一段时间两两相遇，按照剪刀石头布的规则，可能会有一人淘汰出局。
问最终三个阵营获胜的概率。

题解：

$dp[i][j][k]$ :剩下 $i$ 个石头， $j$ 个剪刀， $k$ 个步的概率
$dp[x][y][z]=1;$

$x=i*k+j*k+i*j$
石头+布： $dp[i-1][j][k]+=dp[i][j][k]*((i*k)/x)$
石头+剪刀： $dp[i][j-1][k]+=dp[i][j][k]*((i*j)/x)$
剪刀+布： $dp[i][j][k-1]+=dp[i][j][k]*((j*k)/x)$

$ans1=dp[1][0][0]+...dp[x][0][0];$
$ans2=dp[0][1][0]+...dp[0][y][0];$
$ans3=dp[0][0][1]+...dp[0][0][z];$

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=105;
double dp[N][N][N];
void solve()
{
    int x,y,z;
    cin>>x>>y>>z;
    dp[x][y][z]=1;
    for(int i=x;i>=0;i--){
        for(int j=y;j>=0;j--){
            for(int k=z;k>=0;k--){
                double num=(i*j)+(i*k)+(j*k);
                if(num==0.0)continue;
                if(i-1>=0)dp[i-1][j][k]+=dp[i][j][k]*(double(i*k*1.0)/num);
                if(j-1>=0)dp[i][j-1][k]+=dp[i][j][k]*(double(i*j*1.0)/num);
                if(k-1>=0)dp[i][j][k-1]+=dp[i][j][k]*(double(j*k*1.0)/num);
            }
        }
    }
    double ans1=0.0,ans2=0.0,ans3=0.0;
    for(int i=1;i<=x;i++)ans1+=dp[i][0][0];
    for(int i=1;i<=y;i++)ans2+=dp[0][i][0];
    for(int i=1;i<=z;i++)ans3+=dp[0][0][i];
    cout<<fixed<<setprecision(10)<<ans1<<' '<<ans2<<' '<<ans3<<endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

9. Codeforces 498B

题意：

在一场猜歌游戏中，n首歌按顺序播放，猜中一首歌后直接播放下一首。
第i首歌在ti秒内的猜中概率为pi，在ti秒后的猜中概率为100%，ti为最大播放时长，ti为最大播放时长。问T秒内猜中歌曲数量的期望。

题解：

AC代码：

#include <bits\stdc++.h>
using namespace std;
const int N = 5001;
int t[N];
double p[N];
double dp[N][N];

int main() {
    int n, T;
    cin >> n >> T;
    for(int i = 1 ; i <= n ; i++){
        cin >> p[i] >> t[i];
        p[i] /= 100;
    }
    dp[0][0] = 1;
    double res = 0;
    for (int i = 1; i <= n; i++)
    {
        double ans = 0, tp = pow(1 - p[i], t[i]);
        for (int j = i; j <= T; j++)
        {
            ans += dp[i - 1][j - 1];
            if (j - t[i] >= 1)
                ans -= dp[i - 1][j - t[i] - 1] * tp;
            dp[i][j] = ans * p[i];
            if (j - t[i] >= 0)
                dp[i][j] += dp[i - 1][j - t[i]] * tp;
            ans *= 1 - p[i];
            res += dp[i][j];
        }
    }
    cout << fixed << setprecision(9) << res << endl;
    return 0;
}