题目链接:D-排名估算_牛客挑战赛36 (nowcoder.com)
分析 / Analyse
看完题意有点懵,我们来分析一下,一共有n个人,已知抽了m次都没有比排名比自己高的,不妨将“已知事件”的设为事件A:“抽了m次都没抽中比自己高的”。
而抽人的前提是自己有一个排名,所以我们可以设事件Xi为“当前排名为i“,而在没有事件A的前提下,排名是均匀随机的,所以P(Xi) = 1 / n。
我们要求的是\(E(X | A) = \sum_{i = 1}^{i = n}XiP(Xi | A)\),那么就要求P(Xi | A),但是这个不好求,可以通过贝叶斯公式转换一下,先求P(A | Xi),这个是好求的,它的意义是在已知自己的第i名的条件下,抽m次,一次没抽中的概率,不难计算得
\(P(A | X_i) = (\frac{n - i}{n - 1}) ^ m\)
每一次抽都是独立事件,而每一次都抽到了在i后面的这n - i个人。
好,现在我们求到了P(A | Xi),那么通过贝叶斯公式可以得到P(Xi | A),如下:
接下来将P(A | Xi)代入即可得到如下的式子:
最后的式子就是答案,因为n特别大,所以要用拉格朗日插值求这个有穷级数(类似自然数幂和,其实这个式子可以化为从0到n-1的自然数幂和,令j=n-i即可)。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 5007, p = 998244353; int fac[maxn], y[maxn]; int qmi(int a,int b) { int res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p, b >>= 1; } return res; } int mo(int x){return (x % p + p) % p;} int lagrange(int n,int k)//sum[1, n], (n - i) ^ k { static int y[maxn], fac[maxn]; fac[0] = 1, y[0] = 0; for(int i = 1;i <= k + 2; ++ i)fac[i] = fac[i - 1] * i % p; for(int i = 1;i <= k + 2; ++ i)y[i] = mo(y[i - 1] + qmi(mo(n - i), k)); if(n <= k + 2)return y[n]; int pro = 1; for(int i = 1;i <= k + 2; ++ i)pro = mo(pro * mo(n - i));//求出拉格朗日系数分子的累乘 int res = 0; for(int i = 1;i <= k + 2; ++ i) { int up = mo(pro * qmi(mo(n - i), p - 2)); int down = mo(fac[i - 1] * fac[k + 2 - i]); int sig = (k + 2 - i) % 2 == 0 ? 1 : -1; res = mo(res + mo(sig * y[i] % p * up % p * qmi(down, p - 2) % p)); } return res; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m;cin >> n >> m; int up = lagrange(n, m + 1), down = lagrange(n, m); int ans = mo(n % p - up * qmi(down, p - 2) % p); cout << ans << '\n'; return 0; }
Comments NOTHING