[牛客挑战赛36]D.排名估算（概率期望 + 拉格朗日插值）

题目链接：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;
}