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

发布于 2022-11-09  254 次阅读


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