search

概率DP

hashtag
走路

蜗蜗的世界里有 n 个城市，城市之间通过 m 条单向高速公路连接，初始他在 1 号城市。蜗蜗想去 n 号城市游玩，假设现在他在 x 号城市，他会等概率地选择从 x 出发的高速公路中的一条走过去。如果没有任何从 x 号城里出发的高速公路，他就只能留在原地了。蜗蜗会一直走直到他无路可走。

请问蜗蜗有多大的概率能够走到 n 号城市。

用f[x]表示能走到x号城市的概率，f[1]=1；

考虑从x号城市出发到y号城市，通过x号城市走到y号城市的概率为f[y]+=\frac{f[x]}{d[x]},其中d[x]表示从x号城市出发的高速公路一共有多少条

则能走到y号城市的概率为f[y]=\sum_{x\epsilon pre[y]} \frac{f[x]}{d[x]} ，pre[x]表示所有连接到y号城市的高速公路的起点的集合

int n, m, d[101];
vector<int>c[101];
double f[1001];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        c[x].push_back(y);
        d[x]++;
    }
    memset(f, 0, sizeof(f));
    f[1] = 1;
    for (int i = 1; i <= n; i++) {
        for (auto j : c[i]) {
            f[j] += f[i] / d[i];
        }
    }
    printf("%.10f", f[n]);
    return 0;
}

hashtag
走路2

蜗蜗的世界里有 n 个城市，城市之间通过 m 条单向高速公路连接，初始他在 1 号城市。蜗蜗想去 n 号城市游玩，假设现在他在 x 号城市，他会等概率地选择从 x 出发的高速公路中的一条走过去。如果没有任何从 xx 号城里出发的高速公路，他就只能留在原地了。蜗蜗会一直走直到他无路可走。

请问蜗蜗有多大的概率能够走到 n 号城市。

由于答案是分数，请输出答案mod 1e9+7

这道题就是在走路1的基础上加了一个取模运算，直接用逆元就行

hashtag
走路3

蜗蜗的世界里有 n 个城市，城市之间通过 m 条单向高速公路连接，初始他在 1 号城市。蜗蜗想去 n 号城市游玩，假设现在他在 xx 号城市，他会等概率地选择从 x 出发的高速公路中的一条走过去。如果没有任何从 x 号城市出发的高速公路，他就只能留在原地了。蜗蜗会一直走直到他走到 n 号城市。

请问蜗蜗期望经过多少条高速公路能够走到 n 号城市。

由于答案是分数，请输出答案 mod 1 e 9+7。

期望定义：E(x)=\sum_{i}^{n}x_{i}p_{i}

只要分别计算出经过1条，2条……n-1条高速公路走到n号城市的概率，就可以算出期望

用f[i][j]表示经过j条高速走到i号城市的概率，有：f[i][j]=\sum_{x\epsilon pre[i]}\frac{f[x][j-1]}{d[x]}

最后答案等于\sum_{i=1}^{n-1}f[n][i]*i

更快的方法

用f[x]表示从x号城市出发期望经过多少条高速公路能够到达n号城市，f[n]=0;

考虑期望定义：E(x)=\sum_{i}^{n}x_{i}p_{i},有f[x]=\sum_{y\epsilon nxt(x)}\frac{f[y]+1}{d[x]}=\sum_{y\epsilon nxt(x)}\frac{f[y]}{d[x]}+1

其中nxt(x)表示所有从x出发的高速公路的终点的集合

hashtag
瓜子

小 L 买了 n 粒瓜子。

小L 每次都会从这堆瓜子中挑出一粒，他每次吃完一粒瓜子后，就会得到两瓣瓜子壳，他会把瓜子壳也丢进瓜子堆里面去。

如果他拿到了自己之前吃瓜子留下的瓜子壳，他就会把拿到的瓜子壳丢掉，否则就吃掉拿到的瓜子并且把瓜子壳丢进去。

现在设每次 小L 拿到每一粒瓜子或者是瓜子壳的概率是均等的，问 小L 期望多少次能够把瓜子拿完。

一行一个整数表示结果对于 998244353 取模的结果。如果答案可以被表示成分数p/q，其中p,q互质，那么输出一个数字r，满足q*r≡p(mod998244353)。

用f[i][j]表示还剩下i粒瓜子和j瓣瓜子壳时期望多少次能把瓜子拿完，f[0][j]=0;

那么f[i][j]=\frac{i}{i+j}(f[i-1][j+2]+1)+\frac{j}{i+j}(f[i][j-1]+1)

也就是f[i][j]=\frac{i}{i+j}f[i-1][j+2]+\frac{j}{i+j}f[i][j-1]+1

最后答案为f[n][0]

hashtag
打麻将

I-Chiitoitsu_"蔚来杯"2022牛客暑期多校训练营1 (nowcoder.com)arrow-up-right

题意：共34种牌，每种4张，起始时手里有13张牌，每次摸一张牌后选取最优策略打出一张，打出的牌不能再被摸取，当手中的14张牌全为对子时结束，求结束时摸牌数的期望。

分析：

每次摸牌后打出，要采取最优策略，即为摸到能够组成对子的，就打出一张单数牌，否则丢弃摸到的牌

用dp[i][j]表示手中有i对对子，牌堆中还剩j张牌时的期望

那么每次手中不能组成对子的单数牌的数量single=13-2*i

对于每种情况下的dp[i][j]，只有拿到能够组成对子的和不能组成对子的两种情况

dp[i][j]=\frac{3*single}{j}dp[i+1][j-1]+\frac{j-3*single}{j}dp[i][j-1]+1

用cnt表示初始情况下手中对子的数量，dp[cnt][123]就是最终答案

Last updated