首页 > 其他分享 >【XSY3898】强度(期望dp)

【XSY3898】强度(期望dp)

时间:2022-10-30 14:14:55浏览次数:62  
标签:期望 子树内 big int XSY3898 sum Epsilon operatorname dp

题面

强度

题解

首先题目的要求肯定要转化。

有多种转化方法,例如:(其中 \(s_i\) 代表以 \(i\) 为根节点的子树大小)

\[\begin{aligned} \Epsilon(w(T))=&\Epsilon\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{dist}_T(i,j)\right)\\ =&\Epsilon\left(\sum_{i=2}^n s_i\left(n-s_i\right)\right)\\ =&\Epsilon\left(\sum_{i=2}^n ns_i-s_i^2\right)\\ =&n\sum_{i=2}^n\Epsilon(s_i)-\sum_{i=2}^n\Epsilon(s_i^2) \end{aligned} \]

这种做法实际上是对于每一条边统计这条边的贡献。

注意 \(\Epsilon(s_i^2)\neq \Epsilon(s_i)^2\)。而且除了 \(a,b\) 相互独立互不干扰的情况以外,都有 \(\Epsilon(ab)\neq \Epsilon(a)\Epsilon(b)\)。

然后你发现 \(\Epsilon(s_i^2)\) 并不好求。

(其实是可以求的,而且有人过了,但我不会)

所以我们考虑另一种转化方法:(其中 \(d_i\) 代表 \(i\) 节点的深度)

\[\begin{aligned} \Epsilon(w(T))=&\Epsilon\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{dist}_T(i,j)\right)\\ =&\Epsilon\left(\sum_{i=1}^{n}\sum_{j=1}^{n}d_i+d_j-2\times d_{\operatorname{lca}(i,j)}\right)\\ =&\sum_{i=1}^n\sum_{j=1}^n\Epsilon(d_i)+\Epsilon(d_j)-2\sum_{i=1}^n\sum_{j=1}^n\Epsilon(d_{\operatorname{lca}(i,j)})\\ =&2\sum_{i=1}^n\Epsilon(d_i)-2\sum_{u=1}^n\Epsilon(d_u)\sum_{i=1}^n\sum_{j=1}^nP\big[\operatorname{lca}(i,j)=u\big] \end{aligned} \]

这种做法实际上是对于每一个点对统计贡献。

注意到 \(\Epsilon(d_i)\) 是可以通过 DP 容易得到的,那么只需考虑 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^nP\big[\operatorname{lca}(i,j)=u\big]\)。

设 \(u\) 的可能的后代的集合为 \(pos_u\),设 \(v\) 成为 \(u\) 的后代的概率为 \(p_{u,v}\)。这些都可以预处理出来。

设 \(f_u=\sum\limits_{i=1}^n\sum\limits_{j=1}^nP\big[\operatorname{lca}(i,j)=u\big]\),那么最自然的想法是这样容斥:

\[f_u=\Epsilon(s_u^2)-\sum_{v\in pos_u}p_{u,v}f_v \]

但你发现这样好像还是要把 \(\Epsilon(s_u^2)\) 算出来(

怎么办?

有另一种奇怪的计算方式:

考虑按照题目的方法生成两棵树 \(T_1\) 和 \(T_2\)。\(T_1\) 和 \(T_2\) 无需满足任何关系,它们是相互独立的。

考虑在 \(T_1\) 中选出 \(u\) 子树内的一个点 \(x\)、在 \(T_2\) 中选出 \(u\) 子树内的一个点 \(y\) 的 \((x,y)\) 的方案数的期望,显然为 \(\Epsilon(s_u)^2\)。

设 \(g_u\) 表示:

在 \(T_1\) 中选出 \(u\) 子树内的一个点 \(x\)、在 \(T_2\) 中选出 \(u\) 子树内的一个点 \(y\)、

且需要满足 \(T_1\) 中 \(x\to u\) 路径上的点和 \(T_2\) 中 \(y\to u\) 路径上的点除了 \(u\) 之外互不重复

的 \((x,y)\) 的方案数的期望。

那么有转移:

\[g_u=\Epsilon(s_u)^2-\sum_{v\in pos_u}p_{u,v}^2 g_v \]

其中:

  • \(\Epsilon(s_u)^2\) 表示在 \(T_1\) 中选出 \(u\) 子树内的一个点 \(x\)、在 \(T_2\) 中选出 \(u\) 子树内的一个点 \(y\) 的 \((x,y)\) 的方案数的期望。显然这样任意选取并不能保证上面说的两条路径上的点除了 \(u\) 之外不重复,所以要减去一些不合法的方案。

  • \(\sum\limits_{v\in pos_u}\) 枚举的是 \(T_1\) 中 \(x\to u\) 路径上的点和 \(T_2\) 中 \(y\to u\) 路径上的点从 \(v\) 开始重复了。(即 \(T_1\) 中 \(x\to v\) 路径上的点和 \(T_2\) 中 \(y\to v\) 路径上的点除了 \(v\) 之外都还没出现重复)

  • \(p_{u,v}^2\) 代表 \(v\) 在 \(T_1\)、\(T_2\) 中都是 \(u\) 的后代的概率,显然这样就能保证 \(x\)、\(y\) 在 \(T_1\)、\(T_2\) 中都分别是 \(u\) 的后代。

  • \(g_v\) 代表枚举的这种情况的方案数的期望。

然后你发现 \(f_u\) 和 \(g_u\) 其实是一个东西。

然后求出来即可。

#include<bits/stdc++.h>

#define N 300010

using namespace std;

namespace modular
{
	int mod;
	inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
	inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
	inline int mul(int x,int y){return 1ll*x*y%mod;}
}using namespace modular;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

inline int poww(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}

int n,d[N],inv[N],p[N],f[N];
int ans;

vector<int>pre[N];

int main()
{
	n=read();
	mod=read();
	for(int i=1;i<=n;i++)
		for(int j=i+i;j<=n;j+=i)
			pre[j].push_back(i);
	for(int i=2;i<=n;i++)
	{
		int size=pre[i].size();
		for(int j=0;j<size;j++)
			d[i]=add(d[i],add(d[pre[i][j]],1));
		inv[i]=poww(size,mod-2);
		d[i]=mul(d[i],inv[i]);
		ans=add(ans,mul(2,mul(n,d[i])));
	}
	for(int i=n;i>=1;i--)
	{
		int m=n/i;
		p[1]=1;
		int sum=p[1];
		for(int j=2;j<=m;j++)
		{
			p[j]=0;
			for(int k=0,size=pre[j].size();k<size;k++)
				p[j]=add(p[j],p[pre[j][k]]);
			p[j]=mul(p[j],inv[i*j]);
			sum=add(sum,p[j]);
		}
		f[i]=mul(sum,sum);
		for(int j=2;j<=m;j++)
			f[i]=dec(f[i],mul(mul(p[j],p[j]),f[i*j]));
		ans=dec(ans,mul(mul(2,d[i]),f[i]));
	}
	printf("%d\n",ans);
	return 0;
}
/*
3 998244353
*/
/*
5 998244353
*/

标签:期望,子树内,big,int,XSY3898,sum,Epsilon,operatorname,dp
From: https://www.cnblogs.com/ez-lcw/p/16841165.html

相关文章

  • 【XSY3896】相似(dp套dp,状压)
    题面相似题解可以发现,\(S\)和\(T\)相似,等价于它们的最长公共子序列长度至少为\(n-k\)。首先考虑如何求出两个字符串的\(\text{LCS}\)(最长公共子序列)。考虑dp:......
  • 【XSY3892】【hihocoder1147】时空阵(分层图dp)
    设\(dp(i,t,l)\)表示已经定好前\(i\)层,共有\(t\)个节点,其中第\(i\)层有\(l\)个节点。直接转移即可,注意一些细节:第\(1\)层只有\(1\)号节点。同层之间......
  • wordpress编辑器增加粘贴图片上传服务器教程
    默认的编辑器没有粘贴上传图片功能,现在我们来增加一下安装插件网站后台,找到安装插件界面【插件-安装插件-搜索】 ThePaste  测试插件发布文章的时候,直接使用qq......
  • 【XSY3633】匹配(树形 DP,树链剖分,分治)
    考虑最普通的DP:设\(f_{u,i,0/1}\)表示\(u\)子树内恰好包含\(i\)条边的最大权匹配,其中\(u\)有无被匹配。这是个树上背包,暴力DP是\(O(n^2)\)的。可以发现\(f......
  • 【XSY3535】购物(决策单调性优化DP,分治,结论,背包)
    题面购物题解决策单调性全忘了……先考虑暴力怎么做,我们可以设\(f_{i,j}\)表示前\(i\)个商店买了\(j\)件物品的最小代价,然后有转移:\[f_{i,j}=\min_{k=0}^j(f_{i......
  • 【XSY3513】Multiple of Nine(状压DP)
    题意:转化后变为:给一张\(n\)个点的图,你需要给每个点染上\([1,k]\)中的某个颜色,图上有\(m\)条边,每条边\((u,v)\)有两种边权\(w_1\)(当\(u,v\)颜色相同时)和\(w_2\)......
  • 【XSY3409】树(概率与期望,思维)
    考虑累加种下第\(i\)棵不同的树树到种下第\(i+1\)棵不同的树之间的时间间隔,设\(f(i)\)表示种了\(i\)棵不同的树游戏仍未结束的概率,那么有:\[\begin{aligned}ans&=......
  • (美化)WordPress网站添加自定义字体
    背景通过CSS属性@font-face和font-family可以实现加载自定义webfont,改变网页字体,实现美化效果。1.引用字体文件出于版权风险考虑,尽量使用免费可商用的字体作为webfont。本......
  • wordpress网站主题安装教程
    前面已经搭建好了网站,但是默认的页面比较简陋,我们需要更改一下外观现在我们安装新的主题外观,使网站更加的好看下载主题https://www.lovestu.com/corepress-free可以使......
  • 【XSY3270】Domino Colorings(轮廓线dp,状压)
    若已经知道了每个格子的颜色,我们可以用轮廓线DP(类似插头DP)判断棋盘是否能被多米诺骨牌填满,设\(dp[S]\)表示是否存在某种填法使得轮廓线每个位置是否被填的状态为\(S\)......