[AGC047D] Twin Binary Trees 题解

观察到答案可以表示为：其中

v_i

表示

i

到根编号的乘积。

\sum_{i}\sum_j \frac{v_i\times v_j\times v_{p_i}\times v_{p_j}}{v_{lca(i,j)}\times v_{fa\_lca(i,j)}\times v_{lca(p_i,p_j)}\times v_{fa\_lca(p_i,p_j)}}

显然可以 dfs 枚举

lca(i,j)

，此时

i,j

分处于两棵子树。然后考虑

p_i,p_j

的贡献。

考虑

p_i

放在原地，然后从

p_j

向上遍历，不难发现每次只需要计算一棵子树内的

p_i

的贡献和，发现

p_i

也可以先向上遍历，并在经过的点上打上标记。

时间复杂度

O(n\log^2 n)

。

#define mo 1000000007
int ksm(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=1ll*ans*x%mo;
		x=1ll*x*x%mo,y>>=1;
	}return ans;
}
#define inc(x,y) (x+=y,x-=x>=mo?mo:0)
#define dec(x,y) (x-=y,x+=x<0?mo:0)
const int N=4e5+5;
int n,m,o,a[N],v[N],iv[N],ans,f[N],vv[N];
#define mid ((l+r)>>1)
void dfs(int x,int l,int r)
{
	if(l==r)return;
	dfs(x<<1,l,mid),dfs(x<<1|1,mid+1,r);
	fo(i,l,mid)
	{
		for(rg j=a[i];j;j>>=1)inc(f[j],vv[i]);
	}
	int s=0;
	fo(i,mid+1,r)
	{
		for(rg k=a[i],j=a[i]>>1;j;j>>=1,k>>=1)inc(s,1ll*f[k^1]*vv[i]%mo*iv[j]%mo*iv[j>>1]%mo);
	}
	inc(ans,1ll*s*iv[x]%mo*iv[x>>1]%mo);
	fo(i,l,mid)
	{
		for(rg j=a[i];j;j>>=1)f[j]=0;
	}
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>m,n=(1<<m)-1,o=(1<<m>>1)-1,m=o+1;
	fo(i,o+1,o+m)cin>>a[i],a[i]+=o;
	v[0]=1,iv[0]=1;
	fo(i,1,n)
	{
		v[i]=1;
		for(rg j=i;j;j>>=1)v[i]=1ll*v[i]*j%mo;
		iv[i]=ksm(v[i],mo-2);
	}
	fo(i,o+1,o+m)vv[i]=1ll*v[i]*v[a[i]]%mo;
	dfs(1,o+1,o+m);
	cout<<ans;
	return 0;
}

[AGC047D] Twin Binary Trees 题解

文章操作

相关推荐

评论

[AGC047D] Twin Binary Trees 题解