HZOJ
(弱化版)arc195e
写在前面
比一堆计数还史的模拟赛是一堆求期望的模拟赛。评价和心情均如本场T3题目名称：好难。
名字（name）题解
题意
给定点数\(n\)和系数\(a_i, b_i\)进行建树，每个点的父亲可以是编号比自己小的点，以\(j\) 号点为父亲的概率是\(\frac{a_j}{\sum_{k=1}^{i-1}a_k}\)，且连接父子节点边的权值是\(b_i+b_j\)。给出\(q\) 个询问，求问给出的两点间距离的期望值。
赛时开始觉得枚举中转点的结论是错的，已经开始把第一个subtask的数据范围开始画所有可能的树然后手算了，结果式子写着写着就发现有点规律，反正推得有点累了就寻思着试试写一下吧，没想到居然是对的，喜提30pts。测第二个subtask数据范围的数据发现就差一点点点点点点点点点点点点点就能过极限数据了，结果卡半天时发现实在是无能为力，遗憾离场。
正解的思路是先将\(dis_{u,v}\) 转化为\(dep_u+dep_v-2*dep_{lca(u,v)}\)。
定义\(qzha_i\) 为第\(i\) 个位置的\(a_i\) 的前缀和。
首先求\(E(dep_i)\)。很显然，\(dep_i=\sum_{j=1}^{i-1}\frac{a_j}{qzha_{i-1}} (dep_j+b_i+b_j)\)。直接求显然是\(O(n^2)\) 的，考虑优化。将式子化为\(\frac{1}{qzha_{i-1}}[\sum_{j=1}^{i-1}a_j*(dep_j+b_j)+\sum_{j=1}^{i-1}a_j*b_i]\)。前面一坨可以用前缀和优化，后面一坨显然就等于\(qzha_{i-1}*b_i\)。
至于求\(E(dep_{lca(u,v)})\)，我们钦定\(u<=v\)。有个不显然但是能理解的性质是这个值只与\(u\) 有关，且该值唯一且确定。令\(le_i\) 用于表示该值。因为lca编号一定不大于\(u\)，所以我们只用考虑以\(1~u\)号节点为lca的期望，不用考虑\(u, v\) 间具体有哪些点。根据这条性质我们可以得知对于一个确定的\(u\)，无论\(v\) 的值是多少，lca的期望都是相同的。所以我们考虑将求解\(dep_{lca(u,v)}\) 转化为求\(dep_{lca(u,u+1)}\)，再进一步转化为求\(dep_{lca(i,u) (i<=u)}\)。所以式子就是\(le_i=\sum_{j=1}^{i}\frac{le_j}{qzha_i}\) 化简后前缀和优化就能做到\(O(n)\) 处理。
经历一系列繁琐的处理，最后的结果就为\(dep_u+dep_v-2*le_u\)（注意特判\(u==v\) 的情况）。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+10,mod=1e9+7;
int n,q;
int a[maxn],b[maxn];
int qzha[maxn],dep[maxn],deps[maxn];
int le[maxn],qzhle[maxn];
inline int qpow(int x,int y){int res=1;while(y){if(y&1) res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;
}
signed main(){freopen("name.in","r",stdin);freopen("name.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1;i<=n;++i) cin>>a[i];for(int i=1;i<=n;++i) cin>>b[i];for(int i=1;i<=n;++i) qzha[i]=qzha[i-1]+a[i];dep[1]=1;deps[1]=1ll*a[1]*(1+b[1])%mod;for(int i=2;i<=n;i++) dep[i]=1ll*(deps[i-1]+1ll*qzha[i-1]*b[i]%mod)%mod*qpow(qzha[i-1],mod-2)%mod,deps[i]=(deps[i-1]+1ll*a[i]*(b[i]+1ll*dep[i])%mod)%mod;qzhle[1]=a[1];le[1]=1;for(int i=2;i<=n;i++) le[i]=1ll*(qzhle[i-1]+1ll*dep[i]*a[i]%mod)*qpow(qzha[i],mod-2)%mod,qzhle[i]=(qzhle[i-1]+1ll*le[i]*a[i]%mod)%mod;for(int i=1,x,y;i<=q;i++){cin>>x>>y;if(x>y) swap(x,y);cout<<(x==y?0:((1ll*dep[x]+dep[y]-2ll*le[x]%mod)%mod+mod)%mod)<<'\n';}return 0;
}