ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年11月9日 138点热度 0人点赞 0条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 拉格朗日插值 期望 概率 算法竞赛 自然数幂和
最后更新:2022年11月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 分析 / Analyse
  • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号