首页 > 其他分享 >概率期望

概率期望

时间:2022-08-18 07:33:11浏览次数:62  
标签:概率 期望 int 灭蚊器 蚊子 兔子 dp mod

蚊子(A4)

作为一只明媚的兔子,要会叠被子,又得会打蚊子…

兔子住在兔子洞里。兔子洞可以看成是一棵无根树,有n个洞穴,有n-1条通道连接着n个洞穴。

每天晚上,兔子会在1号洞穴里缩成一团,睡一觉。同时,蚊子大军出动,去欺负兔子。

因为蚊子人多势众,所以它们分兵m*(m-1)路。m是整个兔子洞中只和一条通道相邻的洞穴数目。任意两个这样的洞穴a,b之间(也就是任意两个叶子节点之间)会有两只蚊子,一只从a飞到b,一只从b飞到a。它们都沿着a到b的最短路径移动。蚊子每秒钟可以通过一条通道。所有蚊子都在0s时突然出现在起点并开始移动。每只蚊子在到达终点后的一瞬间都会突然消失。有些蚊子并不会经过兔子所在的1号节点,它们起到的是恐吓作用。

又一次满脸是包地醒来后,兔子忍无可忍了,于是它找到liu_runda让liu_runda去打蚊子…liu_runda不知所措,于是去某宝搞了一个灭蚊器…这个灭蚊器被放在1号节点。每个时刻,它都会工作一次,把和灭蚊器距离小于等于d范围内的蚊子全部杀死。(d=0时只能控制1号点一个位置)

遗憾的是,兔子洞尚未通电,兔子只能用爱发电。 因此,每个时刻灭蚊器只有p/q的概率能够正常工作。如果不能正常工作,那么蚊子将不受到任何影响。

灭蚊器无法影响出现之前和消失之后的蚊子。但在蚊子出现在起点和消失在终点的那个时刻,如果灭蚊器正常工作且蚊子在作用范围内,这只蚊子仍会被杀死。

兔子对liu_runda的诚意表示怀疑…于是它让liu_runda算出灭蚊器在一晚上期望能杀死多少蚊子。liu_runda当然会算了,但是他想考考你。

因为兔子讨厌小数,你需要输出这个期望值模10^9+7后的结果。

(如果你算错了,就会被liu_runda拿去喂兔子,啊呜~~)

发现杀死蚊子的概率可以转化成蚊子存活的概率。只需要算出存活的期望蚊子数量,用tot*(tot-1)-ans,就是杀死的期望。为什么转化?因为存活的好求,假设有效作用范围内的时间t,某只蚊子的存活概率是\((1-p/q)^t\)。

如果直接枚举每一对蚊子算lca,是\(n^2 log(n)\)我门可以考虑求出以每个非叶子节点为lca的总路径贡献,假设dp[x]:x的叶子的走到目前为止的累计存活概率(因为系数qw是我提前预处理出来,每到达一个有效作用范围都可以继续累加qw这个有效作用时间),目前的fa的贡献就是\(\sum_{i=son}^{} \sum_{j=son}^{} dp[i]*dp[j]*qw(dep_f<=d)\)我们可以利用乘法分配率把\(son*son\)的复杂度降低到O(son)。

const int N=5000000+100;const ll mod=1e9+7;
int n;
int d,p,q,lef;
ll dp[N],ans,xs;
struct node
{
	int to,nxt;
}e[N<<1];
int head[N],tot;
inline void Add(int x,int y)
{
	e[++tot].to=y,e[tot].nxt=head[x];head[x]=tot;
}
inline ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
inline void dfs(int x,int f,int dep)
{
	bool son=0;
	for(rint i=head[x];i;i=e[i].nxt)
	{
		int to=e[i].to;
		if(to==f)continue;
		dfs(to,x,dep+1);son=1;
		dp[x]+=dp[to];
		dp[x]%=mod;
	}
	if(!son)
	{
		lef++;dp[x]=1;
	}
	ll now=((dep>d)?1:(xs));
	for(rint i=head[x];i;i=e[i].nxt)
	{
		int to=e[i].to;
		if(to==f)continue;
		ans=(ans+(dp[x]-dp[to]+mod)*dp[to]%mod*now%mod)%mod;
	}
	dp[x]=dp[x]*now%mod;
}
signed main()
{
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	n=re();
	_f(i,1,n-1)
	{
		int fr=re(),to=re();Add(fr,to);Add(to,fr);
	}
	d=re(),p=re(),q=re();
	xs=(1LL+mod-qpow(q,mod-2)*p%mod)%mod;
	dfs(1,0,0);
	chu("%lld",(lef*(lef-1)%mod-ans+mod)%mod);//??
	return 0;
}

标签:概率,期望,int,灭蚊器,蚊子,兔子,dp,mod
From: https://www.cnblogs.com/403caorong/p/16597456.html

相关文章

  • Chiitoitsu(概率DP)
    代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>usingnamespacestd;typedeflonglongll;constintN=1......
  • 期望dp
    期望的线性性质:E(ax+by)=aE(X)+bE(Y)1-n总长度的期望到达某个结果的期望值=这个结果*从起始状态到这个状态的概率f[i]=∑1/k*(w[i]+f(S[i])f[i]表示从i走到n的期......