[概率DP]相逢是温厚

题意

有\(n\)场比赛，他每次等概率地选择一场，选择的比赛可能有没ac过的题，他一定会ac这次比赛中的某一道，并说我好菜啊。如果全ac过了，也会说我好菜啊。求期望说多少次我好菜啊。

注意题目中每场题的范围是1到3

我们可以把相同题数的场看成同一种，那就有三种

把题意抽象成取球游戏，就是\(i_1\)类型的球有\(a_1\)个，\(i_2\)类型的球有\(a_2\)个，\(i_3\)类型的球有\(a_3\)个，即将数量一样的比赛抽象成同一种球，问期望用多少次可以取到所有不同的球。不同种类的球取出会带来不同的变化，取了\(i_1\)类型的球会导致剩余没取的个数减一，但取了\(i_3\)类型的球因为这个比赛的题目数减一变成\(i_2\)类型，取了\(i_2\)类型的球就变成\(i_1\)类型的。

这个问题挺难的，那我们就先看一下最基本的取球游戏(彩票收集问题)

前序知识

最基本的取球问题就是\(n\)个球，求将每个球至少取一次，问期望用多少次可以取到所有不同的球。

假设现在还剩下\(i\)个球没取过，那么这时取到没取过的球的概率是

\(P=i / N\)

由于这个事件满足几何分布，所以他的期望就是\(1/p\)，就是\(N/i\)

几何分布（Geometric distribution）是离散型概率分布。其中一种定义为：在n次伯努利试验中，试验k次才得到第一次成功的机率。详细地说，是：前k-1次皆失败，第k次成功的概率。

用\(dp[i]\)表示剩下\(i\)个球没取时多少次取到剩下所有不同的球的期望

那么可以得出一下递推式：

\[dp[0]=0
\]

由期望的可加性：

\[dp[i]=N/i+dp[i-1]
\]

本题题解

这题就是取球游戏改编的，但是状态比较多，变成了3维的

根据上面的递推式和本题题意，得出以下状态转移方程，令\(dp[i][j][k]\)为剩下三种球没取时多少次取到所有不同的球的期望。再令\(M=i+j+k\)

\[dp[0][0][0]=0
\]

因为当前的状态有三种可能状态转移，并且每场比赛的选择都是等概率的，将后继状态已经求出的期望加上当前状态取出不同的球的期望。

\[dp[i][j][k]=N/M+dp[i-1][j][k]* i/M+dp[i+1][j-1][k] * j/M+dp[i][j+1][k-1]* k/M
\]

化简一下就是(好像没怎么化简)

\[dp[i][j][k]=(N+dp[i-1][j][k] * i+dp[i+1][j-1][k] * j+dp[i][j+1][k-1] * k)/M
\]

代码

可以将\(k\)优化一下，枚举所有的状态，然后暴力转移

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn = 505;

const int mod=17680321;

ll inv[maxn];

ll num[4];

ll dp[maxn][maxn][2];

void init(int n){

    inv[1]=1;

    for(int i=2;i<=n;++i){

        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

    }

}

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    int n;

    cin>>n;

    init(n);

    for(int i=1,a;i<=n;++i) {

        cin>>a;

        num[a]++;

    }

    dp[0][0][0]=0;

    int t=1;

    for (int k = 0; k <= num[3]; k++) {

        t ^= 1;

        for (int j = 0; j +k<= n; j++){

            for (int i = 0; i +k+j<= n; i++){

                if (i || j || k) {

                    dp[i][j][t] = 1ll * n * inv[i + j + k] % mod;

                    if (i)dp[i][j][t] = (dp[i][j][t] + 1ll * dp[i - 1][j][t] * i % mod * inv[i + j + k]) % mod;

                    if (j)dp[i][j][t] = (dp[i][j][t] + 1ll * dp[i + 1][j - 1][t] * j % mod * inv[i + j + k]) % mod;

                    if (k)dp[i][j][t] = (dp[i][j][t] + 1ll * dp[i][j + 1][t ^ 1] * k % mod * inv[i + j + k]) % mod;

                }

            }

        }

    }

    cout<<dp[num[1]][num[2]][t]<<endl;

    return 0 ;

}

总结

与常规的求解不同，数学期望经常逆向推出。

常言道："正向推概率，反向推期望"

为什么呢？

大家可以百度一下（逃

博客：https://www.cnblogs.com/smallocean/

巴特西

[概率DP]相逢是温厚

题意

前序知识

本题题解

代码

总结

最新文章

热门文章