[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;
}