概率DP
走路
蜗蜗的世界里有 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;
}走路2
蜗蜗的世界里有 n 个城市，城市之间通过 m 条单向高速公路连接，初始他在 1 号城市。蜗蜗想去 n 号城市游玩，假设现在他在 x 号城市，他会等概率地选择从 x 出发的高速公路中的一条走过去。如果没有任何从 xx 号城里出发的高速公路，他就只能留在原地了。蜗蜗会一直走直到他无路可走。
请问蜗蜗有多大的概率能够走到 n 号城市。
由于答案是分数，请输出答案
mod 1e9+7
这道题就是在走路1的基础上加了一个取模运算，直接用逆元就行
int n, m, d[101];
vector<int>c[101];
ll f[1001];
const int p = 1e9 + 7;
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b /= 2;
}
return ans;
}
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[j] + f[i] * qpow(d[i], p - 2)) % p;
}
}
f[n] %= p;
printf("%lld", f[n]);
return 0;
}走路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
int n, m, d[101];
vector<int>c[101];
ll f[101][101];
const int p = 1e9 + 7;
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b /= 2;
}
return ans;
}
signed 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][0] = 1;
for (int i = 1; i <= n; i++) {
for (int k = 0; k < n; k++) {
if (f[i][k]) {
for (auto j : c[i]) {
f[j][k+1] = (f[j][k+1] + f[i][k] * qpow(d[i], p - 2)) % p;
}
}
}
}
ll ans = 0;
for (int i = 1; i < n; i++) {
ans = (ans + f[n][i] * i) % p;
}
cout << ans << endl;
return 0;
}更快的方法
用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出发的高速公路的终点的集合
int n, m;
vector<int>c[101];
ll f[101];
int d[101];
const int p = 1e9 + 7;
ll qpow(int a, int b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b /= 2;
}
return ans;
}
void solve() {
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));
for (int i = n-1; i ; i--) {
f[i] = 1;
for (auto j : c[i]) {
f[i] = (f[i] + f[j] * qpow(d[i], p - 2)) % p;
}
}
cout << f[1] << endl;
}瓜子
小 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]
int n;
int f[2001][4001], a[4001];
const int p = 998244353;
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
void solve() {
cin >> n;
for (int i = 1; i <= 2*n; i++) a[i] = qpow(i, p - 2);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 2 * n - 2; j++) {
f[i][j] += 1;
f[i][j] += f[i - 1][j + 2] * i % p * a[i + j] % p;
if (j) f[i][j] += f[i][j - 1] * j % p * a[i + j] % p;
}
}
cout << f[n][0];
}打麻将
I-Chiitoitsu_"蔚来杯"2022牛客暑期多校训练营1 (nowcoder.com)
题意：共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]就是最终答案
int dp[8][125];
int inv[126];
const int mod = 1e9 + 7;
int qpow(int a, int b)//快速幂
{
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int askinv(int x) {//求逆元
return qpow(x, mod - 2);
}
signed main()
{
int ed = 136 - 13;
for (int i = 1; i <= 125; i++) inv[i] = askinv(i);
for (int i = 0; i < 125; i++) dp[7][i] = 0;
for (int i = 6; i >= 0; i--) {
int single = 13 - 2 * i;
for (int j = 1; j <= ed; j++) {
ll p1 = 3 * single % mod * inv[j] % mod;
ll p2 = (j - 3 * single) % mod * inv[j] % mod;
dp[i][j] = p1 * dp[i + 1][j - 1] % mod + p2 * dp[i][j - 1] % mod + 1;
dp[i][j] %= mod;
}
}
int T; cin >> T;
for (int i = 1; i <= T;i++) {
string ss; cin >> ss;
set<string>s;
for (int i = 0; i < 25; i=i+2) {
string t;
t += ss[i]; t += ss[i + 1];
s.insert(t);
}
int cnt = 13 - s.size();
printf("Case #%d: %lld\n", i, dp[cnt][ed]);
}
return 0;
}
Last updated