『数学期望』某次模拟赛T1

本文主要是介绍『数学期望』某次模拟赛T1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{Problem}$

在这里插入图片描述

$\mathrm{Solution}$

做一类期望题我们无法确定未来的行为，但是存在未来行为的边界，我们可以选择逆向做期望DP来解决这类问题。

我们设 $f_i$ 表示当前已经取走了i张牌，接下来还要取的期望排数。

那么，我们需要遵循概率和为1的原则列出状态转移方程。

取走已经取走的， $\mathrm P=\frac{i}{n}$ ,由于接下来不取了，期望取 $1$ 次。
取走没有取走的， $\mathrm P=\frac{n-i}{n}$ ,此时取走了 $i + 1$ 张，那么期望当前 $1$ 次，接下来 $f_{i+1}$ 次。

然后就有转移方程： $f[i]=\frac{i}{n}\times 1+\frac{n-i}{n}\times(f[i+1]+1)$

然后我们递推求解即可。

$\mathrm{Code}$

#include <cstdio>
#include <iostream>using namespace std;
const int N = 2e7;
const int P = 998244353;int f[N];int read(void)
{int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}int power(int a,int b) {int res = 1;while (b > 0) {if (b & 1) res = 1LL * res * a % P;a = 1LL * a * a % P, b >>= 1;}return res;
}void write(int x) {if (x > 9) write(x/10);putchar(x%10+48);
}int work(void)
{int n = read(),Inv = power(n,P-2);f[n] = 1;for (int i=n-1;~i;--i) f[i] = (1LL*i*Inv+1LL*(f[i+1]+1)*(n-i)%P*Inv%P)%P;return f[0];
}int main(void) 
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);int T = read();while (T --) {write(work());putchar('\n');}return 0;
}