【2022 NOIP 模拟赛 25】名字 做题记录

给定 $n$ 和两个长度为 $n$ 的正整数数列 $a,b$，以如下方式生成一棵树：

• $u$ 的父亲 $fa_u$ 在 $[1,u-1]$ 中取，取到 $i$ 的概率是 $\frac{a_i}{\sum\limits_{j=1}^{u-1}a_j}$；
• $u$ 和 $fa_u$ 之间有一条长度为 $b_u+b_{fa_u}$ 的边。

$q$ 组询问，每次给出两个点 $x,y$，求 $x,y$ 之间的期望距离对 $10^9+7$ 取模的结果。

$2\le n,q\le 3\times 10^5$，$1\le a_i,b_i\le 3\times 10^3$。

首先由于期望是线性的，所以设 $len_i$ 为 $i$ 到 $1$ 的期望距离，那么 $x,y$ 之间的期望距离即为 $len_x+len_y-2len_{\operatorname{lca}(x,y)}$。

设 $s_i=\sum\limits_{j=1}^{i}a_j$，$len_i$ 显然即为 $\sum\limits_{j=1}^{i-1} \frac{a_j}{s_{i-1}}(len_{j}+b_i+b_j)$，可以前缀和快速求。

考虑求解 $2len_{\operatorname{lca}(x,y)}$，显然求 $len_{\operatorname{lca}(x,y)}$ 再乘上 $2$ 即可。不妨钦定 $x<y$，那么一定有 $\operatorname{lca}(x,y)<x$，考虑让 $y$ 在树上不断往父亲跳，跳到 $y'\le x$ 时停下。设 $y'=i$ 的概率是 $f(i)$，那么有 $f(i)=\frac{a_i}{s_x}$，归纳证明如下：

• 显然从 $x+1$ 开始跳，跳一步就会停下，跳到 $i$ 的概率是 $\frac{a_i}{s_x}$；
• 考虑从 $k$（$k\ge x+2$）开始跳，设下一步跳到 $p\le x$ 的概率是 $w$，跳到 $p>x$ 的概率是 $v$。若 $p\le x$ 则概率就是 $w\times \frac{a_p}{s_x}$，否则由于 $p$ 跳到 $p'\le x$ 的概率是 $\frac{a_{p'}}{s_x}$，所以 $p$ 跳到 $p'\le x$ 的概率是 $v\times \frac{a_{p'}}{s_x}$。那么最后跳到 $p$ 的概率就是 $w\times \frac{a_p}{s_x}+v\times \frac{a_p}{s_x}=\frac{a_p}{s_x}$。

那么若最后 $y$ 跳到了 $x$ 则 $len_{\operatorname{lca}(x,y)}$ 就是 $len_x$，否则设最后跳到了 $p$ 则变成求 $len_{\operatorname{lca}(x,p)}$，可以让 $x$ 不断往父亲跳解决。所以设 $dp_x$ 表示 $len_{\operatorname{lca}(x,y)}$（$y>x$）的期望值，那么有转移：

$dp_{x}=\frac{a_x}{s_x}\times len_x+\sum\limits_{i=1}^{x-1} \frac{a_i}{s_x}\times dp_i$

可以用前缀和快速求，那么做完了。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

#define fio(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)

const int S=300005,p=1000000007;

int n,q,a[S],b[S];
int sm[S],len[S],dp[S];

inline int qpow(int x,int y=p-2)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=(y&1)?1ll*res*x%p:res;
	return res;
}

int main()
{
	fio("name");
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) sm[i]=(sm[i-1]+a[i])%p;
	len[1]=0;
	for(int i=2,val=1ll*a[1]*b[1]%p;i<=n;i++)
	{
		len[i]=(1ll*val*qpow(sm[i-1])%p+b[i])%p;
		val=(val+1ll*a[i]*(len[i]+b[i])%p)%p;
	}
	dp[1]=0;
	for(int i=2,val=0;i<=n;i++)
	{
		dp[i]=1ll*(val+1ll*a[i]*len[i]%p)*qpow(sm[i])%p;
		val=(val+1ll*a[i]*dp[i]%p)%p;
	}
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y)
		{
			puts("0");
			continue;
		}
		if(x>y) swap(x,y);
		printf("%d\n",((len[x]+len[y])%p-2ll*dp[x]%p+p)%p);
	}
	return 0;
}