首页 > 其他分享 >P10227 [COCI 2023/2024 #3] Slučajna Cesta 题解

P10227 [COCI 2023/2024 #3] Slučajna Cesta 题解

时间：2024-05-12 20:41:03浏览次数：23  
标签：begin end P10227 题解 sum pmatrix Slu frac aligned

P10227 [COCI 2023/2024 #3] Slučajna Cesta 题解

知识点

期望 DP，树形（换根） DP，组合数学。

题意分析

一棵树，每个点都有点权，每一条边的方向分布都是等概率的，问从每个点出发，有路走就一直走的情况下，所途径的点的权值总和的期望值。

思路分析

这明显是一个树形 DP，且需要变成换根 DP 才能过得了这题。

先考虑最基础的树形 DP 暴力：那么设 \(f_u\) 表示从点 \(u\) 开始往子节点走，满足有路走就一直走的情况下，所途径的点的权值总和的期望值。

设一个点 \(u\) 有 \(d_u\) 个子节点，那么我们就可以分情况讨论：

对于通向子节点的边能不能走，共有 \(2^{d_u}\) 种情况。

再根据期望的线性性质，计算每个子节点的 DP 值 \(f_v\) 对 \(f_u\) 的贡献，就是下面这个式子：

\[f_v \cdot \frac{\sum_{i=0}^{d_u-1}\frac{\begin{pmatrix}d_u-1\\i\end{pmatrix}}{i+1}}{2^{d_u}} \]

解释一下：\(\frac{\sum_{i=0}^{d_u-1}\frac{\begin{pmatrix}d_u-1\\i\end{pmatrix}}{i+1}}{2^{d_u}}\) 表示从 \(u\) 走到 \(v\) 的概率。其中作为分母的 \(\frac{1}{2^{d_u}}\) 表示总情况数，上面每次枚举的 \(i\) 表示在 \(u\) 能够通向 \(v\) 时，还能通向几个子节点，那么单次去到 \(v\) 的概率就是 \(\frac{1}{i+1}\)，这种情况的数量就是 \(\begin{pmatrix}d_u-1\\i\end{pmatrix}\)，乘起来就是概率。

那么 \(f_u\) 的值就是：

\[v_u + \frac{\sum_{i=0}^{d_u-1}\frac{\begin{pmatrix}d_u-1\\i\end{pmatrix}}{i+1}}{2^{d_u}} \cdot \sum_{(u,v) \in G} f_v \]

那么我们已经可以拿到 Subtask 1 的分了 （卡一卡 Subtask 2 也是轻轻松松）。

但这明显不够，我们力求完美。这个一看就可以化简 （二项式定理随便搞搞），我们这里讲两种方法。

两种方法都得先化到一定程度：发现概率中有一个会变的分母 \(i+1\)，尝试把它转成一个常量。（只化简能化的概率部分）

\[\begin{aligned} & \frac{\sum_{i=0}^{d_u-1}\frac{\begin{pmatrix}d_u-1\\i\end{pmatrix}}{i+1}}{2^{d_u}} \\ & = \frac{\sum_{i=0}^{d_u-1}\frac{(d_u-1)!}{(i+1) \cdot i! \cdot (d_u - i - 1)}}{2^{d_u}} \\ & = \frac{\sum_{i=0}^{d_u-1}\frac{(d_u-1)!}{(i+1)! \cdot (d_u - i - 1)}}{2^{d_u}} \\ & = \frac{\sum_{i=1}^{d_u}\begin{pmatrix}d_u\\i\end{pmatrix}}{d_u \cdot 2^{d_u}} \\ \end{aligned} \]

  1. 二项式定理：

    好了，到这里，一般数学好的同学已经发现上面的 \(\sum_{i=1}^{d_u}\begin{pmatrix}d_u\\i\end{pmatrix}\) 可以用二项式定理了，那我们就先推一下他：

    \[\begin{aligned} & \prod_{i=1}^n (1+a_ix) \\ & = 1 + (\sum_{i=1}^n a_i) \cdot x + (\sum_{i=1}^n \sum_{j=i+1}^n a_i a_j) x^2 + \cdots + (\prod_{i=1}^n a_i) x^n \\ \end{aligned} \]

    在这里只用在题目里的话，设 \(a_i = 1,\forall i\in[1,n]\)，式子变为：

    \[\begin{aligned} \prod_{i=1}^n (1+a_ix) & = 1 + (\sum_{i=1}^n a_i) \cdot x + (\sum_{i=1}^n \sum_{j=i+1}^n a_i a_j) x^2 + \cdots + (\prod_{i=1}^n a_i) x^n \\ (1+x)^n & = 1 + \begin{pmatrix} n \\ 1 \end{pmatrix} x + \begin{pmatrix} n \\ 2 \end{pmatrix} x^2 + \cdots +\begin{pmatrix} n \\ n \end{pmatrix} x^n \\ (1+x)^n & = \sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} x^i \end{aligned} \]

    这个时候，再设 \(x=1\)，式子就变成了我们想要的样子：

    \[\begin{aligned} (1+x)^n & = \sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} x^i \\ (1+1)^n & = \sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} 1^i \\ 2^n & = \sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} \\ \end{aligned} \]

    于是，我们上面的概率就变成了：

    \[\begin{aligned} & \frac{\sum_{i=1}^{d_u}\begin{pmatrix}d_u\\i\end{pmatrix}}{d_u \cdot 2^{d_u}} \\ & = \frac{2^{d_u}-1}{d_u \cdot 2^{d_u}} \\ \end{aligned} \]

  2. 手推递推式：

    想不到上面这种方法的同学也不要气馁，车到山前必有路，我们再想想。如果实在想不出来，可以试试先做一下这题，我就是受这题莫队方法的启发（不会莫队的同学不必慌张，跟这题没关系）。

    设 \(f_{x,y} = \sum_{i=1}^{x}\begin{pmatrix} y \\ i \end{pmatrix}\)。但是它少一个 \(\begin{pmatrix} y \\ 0 \end{pmatrix}\)，不好处理，那么我们把它加上：设 \(g_{x,y} = \sum_{i=0}^{x}\begin{pmatrix} y \\ i \end{pmatrix}\)，那么显而易见，\(f_{x,y} = g_{x,y} - 1\)。

    我们发现，从 \(g_{x,y}\) 其实可以推出 \(g_{x,y+1}\) 与 \(g_{x+1,y}\)：

    1. \(g_{x,y} \to g_{x,y+1}\)：

      \[\begin{aligned} g_{x,y+1} & = \sum_{i=0}^{x}\begin{pmatrix} y+1 \\ i \end{pmatrix} \\ g_{x,y+1} & = \sum_{i=0}^{x}[\begin{pmatrix} y \\ i \end{pmatrix}+\begin{pmatrix} y \\ i-1 \end{pmatrix}] \\ g_{x,y+1} & = \sum_{i=0}^{x}\begin{pmatrix} y \\ i \end{pmatrix}+ \sum_{i=0}^{x-1} \begin{pmatrix} y \\ i \end{pmatrix} \\ g_{x,y+1} & = 2 g_{x,y} - \begin{pmatrix} y \\ x \end{pmatrix} \\ \end{aligned} \]

    2. \(g_{x,y} \to g_{x+1,y}\)：

      \[\begin{aligned} g_{x+1,y} & = \sum_{i=0}^{x+1}\begin{pmatrix} y \\ i \end{pmatrix} \\ g_{x+1,y} & = \sum_{i=0}^{x}\begin{pmatrix} y \\ i \end{pmatrix} + \begin{pmatrix} y \\ x+1 \end{pmatrix}\\ g_{x+1,y} & = g_{x,y} + \begin{pmatrix} y \\ x+1 \end{pmatrix}\\ \end{aligned} \]

    那么从 \(g_{x,x}\) 就可以推到 \(g_{x+1,x+1}\)：

    \[\begin{aligned} g_{x,x+1} & = 2 g_{x,x} - \begin{pmatrix} x \\ x \end{pmatrix} \\ g_{x+1,x+1} & = g_{x,x+1} + \begin{pmatrix} x+1 \\ x+1 \end{pmatrix} \\ g_{x+1,x+1} & = 2 g_{x,x}\\ \end{aligned} \]

    那么 \(g_{x,x} = 2^x \cdot g_{0,0},g_{0,0}=1\)，即 \(g_{x,x}=2^x,f_{x,x}=2^x-1\)。

    同样也能得出概率为：

    \[\begin{aligned} & \frac{\sum_{i=1}^{d_u}\begin{pmatrix}d_u\\i\end{pmatrix}}{d_u \cdot 2^{d_u}} \\ & = \frac{2^{d_u}-1}{d_u \cdot 2^{d_u}} \\ \end{aligned} \]

总结一下上面的推导过程，得到结论：

\[\begin{aligned} f_u & = v_u + \frac{\sum_{i=0}^{d_u-1}\frac{\begin{pmatrix}d_u-1\\i\end{pmatrix}}{i+1}}{2^{d_u}} \cdot \sum_{(u,v) \in G} f_v \\ f_u & = v_u + \frac{2^{d_u}-1}{d_u \cdot 2^{d_u}} \cdot \sum_{(u,v) \in G} f_v \\ \end{aligned} \]

然后在树形 DP 的基础上再推出换根 DP 就可以拿到满分了！（ヾ(@▽@)ノ欢呼）

时间复杂度在不预处理的情况下是 \(O(n\log_2{P})\) 的，其中 \(P = 10^9 + 7\)，\(\log_2{P}\) 是处理逆元的时间复杂度，但是发现我们所有的逆元都可以 \(O(n)\) 预处理，然后一些其他地方转化一下，就可以去掉这个 \(\log_2{P}\) 了！

CODE

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e6+10;
namespace Modular_Arithmetic{
	#define MOD 1000000007
	#define toadd(a,b) ((a)=add((a),(b)))
	#define tomul(a,b) ((a)=mul((a),(b)))
	int pw[N],pinv[N],Inv[N],val[N];
	template<typename T1,typename T2>constexpr auto add(T1 a,T2 b){
		return a+b>=MOD?a+b-MOD:a+b<0?a+b+MOD:a+b;
	}
	template<typename T1,typename T2>constexpr auto mul(T1 a,T2 b){
		return (long long)a*b%MOD;
	}
	template<typename T,typename...Types>constexpr auto add(T a,Types... b){
		return add(a,add(b...));
	}
	template<typename T,typename...Types>constexpr auto mul(T a,Types... b){
		return mul(a,mul(b...));
	}
	int Pow(int a,int b){
		int res=1;
		for(a%=MOD;b;b>>=1,tomul(a,a))if(b&1)tomul(res,a);
		return res;
	}
	void Init(int n){
		pw[0]=1;
		FOR(i,1,n)pw[i]=mul(pw[i-1],2);
		pinv[n]=Pow(pw[n],MOD-2);
		DOR(i,n,1)pinv[i-1]=mul(pinv[i],2);
		Inv[0]=Inv[1]=1;
	    FOR(i,2,n)Inv[i]=1ll*(MOD-MOD/i)*Inv[MOD%i]%MOD;
	    FOR(i,0,n)val[i]=mul(add(pw[i],-1),Inv[i],pinv[i]);
	}
}using namespace Modular_Arithmetic;
int n;
int a[N],d[N],f[N],h[N];
struct CFS{
	int tot,h[N],v[N<<1],nxt[N<<1];
	void att(int U,int V){
		v[++tot]=V,nxt[tot]=h[U],h[U]=tot;
	}
	void con(int U,int V){
		att(U,V),att(V,U);
	}
}g;
void dfs0(int u,int fa){
	d[u]=0,f[u]=0,h[u]=0;
	EDGE(g,i,u,v)if(v^fa)++d[u],dfs0(v,u),toadd(h[u],f[v]);
	f[u]=add(a[u],mul(h[u],val[d[u]]));
}
void dfs1(int u,int fa){
	if(u>1)++d[u];
	f[u]=add(a[u],mul(h[u],val[d[u]]));
	EDGE(g,i,u,v)if(v^fa)toadd(h[v],add(a[u],mul(add(h[u],-f[v]),val[d[u]-1]))),dfs1(v,u);
}
signed main(){
	rd(n),Init(n);
	FOR(i,2,n){
		int x;
		rd(x),g.con(x,i);
	}
	FOR(i,1,n)rd(a[i]);
	dfs0(1,0),dfs1(1,0);
	FOR(i,1,n)wr(f[i]);
	return 0;
}

提示：把取模运算封装一下会方便很多哦。

标签：begin,end,P10227,题解,sum,pmatrix,Slu,frac,aligned
From： https://www.cnblogs.com/Cat-litter/p/18188153

相关文章

  • [ABC261E] Many Operations 题解
    [ABC261E]ManyOperations题解思路解析首先可以发现，如果直接跑肯定会炸，于是考虑优化。首先发现操作有很多重复的，所以可以考虑把每一个数经过所有操作后的值都预处理下来，但这样显然空间也会炸。然后我们又想到可以不需要求下每个数经过操作后的值，可以把每一位二进制上在开始前......
  • ABC353C Sigma Problem 题解
    ABC353CSigmaProblem题解题目链接：AT题目中的两个求和符号\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\)实际上是在枚举所有的有序数对\((i,j)\)。而有序数对的个数\(N(N-1)/2=O(N^{2})\)，真的去枚举所有数对肯定会T。这时应该考虑去拆贡献，求出每个\(A_i\)对答案的贡献。......
  • 2024江苏省大学生程序设计大赛（JSCPC）热身赛题解（B）
    题目大意：求区间\([l,r]\)中有多少正整数满足\(\phi(\phi(n))=\phi(n)-1\)，其中\(\phi\)为欧拉函数。解：设\(y=\phi(n)\)，则上式变为\(\phi(y)=y-1\)，易证\(y\)为质数（注意\(\phi(1)=1\)，\(1\)与任何正整数都互质）。故原问题转化为求\([l,r]\)中有多少个正整数v满足\(\phi......
  • set 容器详解 附大根堆题解
    声明本文中题解部分内容大部分转载自@sonnety的这篇博客中，本文为为方便复习而写的结论类文章，读者可自行跳转至原文处阅读。PART1set什么是set——来源cppreference简言之，它就是一种存进去就可以自动按升序排列的特殊容器，通常的set还具有自动去重的功能。定义方......
  • 工作疑难问题解决4例
      记录一下工作上疑难问题解决：  一，方便的页面监控     前几天早上，负责的kettle抽取数据表的任务又报错了，早上看手机有4个未接报警电话，一看是人员表，原来昨天报表系统有个大的查询一直未查询完成，导致truncate这个人员表，无法活动meta的锁，后续执行抽取和计算的都报错......
  • U423621 [HDK - NRC] Sqen Paradox 题解
    题目描述及\(O(n^2)\)做法见这个设\(a_i\)表示以\(i\)为左端点，无重复元素的最长区间的左端点，这个直接拿双指针做就行。处理出来后，分类讨论，找\(\max(i-l+1,i-a_i+1)\)，找\(i-l+1\)拿个桶维护一下左端点为\(i\)的右端点有那些就行，剩下的位置找最值即可，这个是RMQ。时间......
  • 工作疑难问题解决4例
      记录一下工作上疑难问题解决：  一，方便的页面监控     前几天早上，负责的kettle抽取数据表的任务又报错了，早上看手机有4个未接报警电话，一看是人员表，原来昨天报表系统有个大的查询一直未查询完成，导致truncate这个人员表，无法活动meta的锁，后续执行抽取和计算的都报错......
  • 第六届·2024 MindSpore 量子计算黑客松热身赛赛题解读
    第六届·2024MindSpore量子计算黑客松火热进行中。本次大赛由量子信息网络产业联盟主办，昇思MindSporeQuantum社区承办，多所高校和单位联合举办。开发者将全面体验全新一代通用量子计算框架MindSporeQuantum。热身赛为量子计算基础学习和编程演练。完成热身赛的前100名选手将有......
  • 题解
    #include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){ intN,m;//N奖金m物品个数cin>>N>>m;N/=10;//由于所有的价格都是10的整倍数，所以可以均除10以简化运算复杂度intprice,priority,hasAttachme......
  • 题解：CF1956A Nene's Game
    这道题其实挺有意思，多测里面还套了个多测。思路就是用向量模拟删除过程，具体请看代码里的注释。#include<bits/stdc++.h>usingnamespacestd;intk,q,a[105];voidsolve(){ intn; cin>>n; vector<int>ve; for(inti=1;i<=n;i++)ve.push_back(i);//把每个人放到向量......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99