bsoj5988 [Achen模拟赛]期望题解

bsoj5988

Description

【题目背景】

　　NOI2018 已经过去了许久，2019 届的 BSOIer 们退役的退役，颓废的颓废，计数能力大不如前。曾经的数数之王 xxyj 坦言：“我现在算期望都靠枚举”，嘴边还挂着什么“分布列”，什么“样本数据”，然后又继续投身于文化课学习中了。

为了让 OI 的火炬传递下去，苣蒻 AChen 决定将 xxyj 退役前随口提到的期望问题交给你来解决。

【题目描述】

　　现有 m + 1 个白色的小球排成一列并从一开始编号。每次操作从前 m 个小球中随机选择一个涂黑。现在执行了 n 次操作，则编号最小的白球编号的期望是多少？

Input

　　从文件 mex.in 中读入数据。

　　输入共一行两个整数 n,m。表示操作次数和白色小球的个数

Output

　　输出到文件 mex.out 中。

　　若最小的白球编号的期望为 E，则输出一行表示：((m^n)* E) mod (10^9 + 7)

　　可以看出上式一定是个整数。

Sample Input

1 1

Sample Output

2

Hint

n <= 10^9, m <= 10^6

Source

Achen

%%%AChen队爷%%%

考察对容斥的基础理解，挺不错的一题

易列答案式

\[\sum_{i=1}^{m+1} P(mex = i) i
\]

对这种期望，常使用套路化法

\[\sum_{i=0}^m P(mex>i)
\]

和式里面相当于要求已钦定$i$个确定的球，求随机选$n$次将这$i$个球全部染黑的概率。

考虑容斥。先随便选，然后减去一个球未染的，然后加上两个球未染的，...

\[\sum_{i=0}^{m} \sum_{k=0}^{i} (-1)^k C_i^k (\frac{m-k}{m})^n
\]

（其实是一个类似二项式反演的容斥）

更换枚举

\[\sum_{k=0}^{m} (-1)^k (\frac{m-k}{m})^n \sum_{i=k}^{m} C_i^k
\]

又由组合数的性质

\[\sum_{i=k}^{n} C_i^k = C_{n+1}^{k+1}
\]

（容易通过杨辉三角和组合数的递推式证明）

得

\[\sum_{k=0}^{m} (-1)^k (\frac{m-k}{m})^n C_{m+1}^{k+1}
\]

直接计算即可。

数据量如果更大的话，可以线筛出所有$n$次幂以省掉快速幂的$\log $。偷懒不写了（

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#include<set>

using namespace std;

typedef long long ll;

const ll MOD=1E9+7;

ll QPow(ll x,ll up){

	x%=MOD;

	ll ans=1;

	while(up)

		if(up%2==0) x=x*x%MOD,up=up/2;

		else ans=ans*x%MOD,up--;

	return ans;

}

ll Inv(ll x){

	return QPow(x,MOD-2);

}

const ll MXN=1E6+5;

ll fac[MXN],facInv[MXN];

void FacInit(ll n){

	fac[0]=1;for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;

	facInv[n]=Inv(fac[n]);for(ll i=n-1;i>=1;i--) facInv[i]=facInv[i+1]*(i+1)%MOD;

	facInv[0]=1;

}

ll C(ll n,ll m){

	if(n<m) return 0;

	return fac[n]*facInv[m]%MOD*facInv[n-m]%MOD;

}

ll N,M;

int main(){

	scanf("%lld%lld",&N,&M);

	FacInit(M+1);

	ll Ans=0;

	for(ll k=0;k<=M;k++){

		ll p=1;if(k%2==1) p=(-1+MOD)%MOD;

		Ans+=p*QPow(M-k,N)%MOD*C(M+1,k+1)%MOD;

		Ans%=MOD;

	}

	printf("%lld",Ans);

	return 0;

}

巴特西

bsoj5988 [Achen模拟赛]期望题解

Description

Input

Output

Sample Input

Sample Output

Hint

Source

最新文章

热门文章

巴特西

bsoj5988 [Achen模拟赛]期望 题解

Description

Input

Output

Sample Input

Sample Output

Hint

Source

最新文章

热门文章

bsoj5988 [Achen模拟赛]期望题解