CF809E Surprise me!解题报告

解题报告

---

CF809E Surprise me!解题报告：

题意

• 给定一棵$n$个点的树，每个点$i$有点权$a_i$（$a$为一个排列），求$\frac{1}{n(n-1)}\sum_{i=1}^n\sum_{j=1}^n dis(i,j)\times \varphi(a_i\times a_j)$。
• 数据范围：$1\leqslant n\leqslant 2\times 10^5$，对$10^9+7$取模。

分析

虽然交不了题解了，但是还是记录一下这道大毒瘤题。

由于$\varphi(a_i)$不太好求，我们考虑$a$是一个排列，因此我们先设$p_{a_i}=i$，即$p$为每个值的位置，然后带进去：

$$\sum_{i=1}^n\sum_{j=1}^n dis(i,j)\times \varphi(a_i\times a_j)=\sum_{i=1}^n\sum_{j=1}^n dis(p_i,p_j)\times \varphi(i\times j)$$

我们首先根据欧拉函数的一个公式$\varphi(n\times m)=\frac{\varphi(n)\times \varphi(m)\times \gcd(n,m)}{\varphi(\gcd(n,m))}$变一下式子（证明在题解末尾），并对于这个式子套路地反演一下（先忽略掉前面的$\frac{1}{n(n-1)}$）：

$$\sum_{i=1}^n\sum_{j=1}^n dis(i,j)\times \varphi(a_i\times a_j)=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)==d]\times dis(p_i,p_j)\times\frac{\varphi(i)\times \varphi(j)\times d}{\varphi(d)}\\=\sum_{d=1}^n \frac{d}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}dis(p_{i\times d},p_{j\times d})\times\varphi(i\times d)\times\varphi(j\times d)\times(\sum_{k\mid\gcd(i,j)}\mu(k))\\=\sum_{d=1}^n\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\frac{d\times \mu(k)}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d\times k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d\times k}\rfloor}dis(p_{i\times d\times k},p_{j\times d\times k})\times\varphi(i\times d\times k)\times\varphi(j\times d\times k)$$

套路地设$T=d\times k$，那么有：

$$\sum_{i=1}^n\sum_{j=1}^n dis(i,j)\times\varphi(a_i\times a_j)=\sum_{T=1}^n(\sum_{d\mid T}\frac{d\times\mu(\frac{T}{d})}{\varphi(d)})\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}dis(p_{i\times T},p_{j\times T})\times \varphi(i\times T)\times \varphi(j\times T)$$

对于前面的东西，我们设$f_x=\sum_{d\mid x}\frac{d\times\mu(\frac{x}{d})}{\varphi(d)}$，这个东西很显然可以先线性筛出来$\varphi$和$\mu$，然后暴力枚举倍数做到$O(n\log n)$求出。

然后，我们把$a_i$和$f$带回原来的式子：

$$\sum_{i=1}^n\sum_{j=1}^n dis(i,j)\times\varphi(a_i\times a_j)=\sum_{T=1}^n f(T)\times\sum_{T\mid a_i}\sum_{T\mid a_j} dis(i,j)\times\varphi(a_i)\times\varphi(a_j)$$

对于后面的东西，我们发现对于每个$T$，用到的点只有$\lfloor\frac{n}{T}\rfloor$个，因此，我们用到的总点数为$\frac{n}{1}+\frac{n}{2}+\cdots\frac{n}{n}=O(n\log n)$个。

如果设$k_i$为第$i$次的总点数，我们有$\sum k_i\leqslant n\log n$，这个数据范围启发我们来建立一颗虚树。

对于每个$T$，我们暴力枚举它的所有倍数的点，建立一颗虚树，然后在上面跑树形$dp$。

具体地，我们设$b_x=[T|x]\varphi(a_x)$，$dp1_i$为$i$子树中的全体贡献，即$dp1_i=\sum_{x\in tree(i)}\sum_{y\in tree(i)}dis(x,y)\times b_x\times b_y$，并设两个辅助数组$dp2_i=\sum_{x\in tree(i)} dis(i,x)\times b_x,dp3_i=\sum_{x\in tree(i)}b_x$。

考虑合并两颗子树$x$和$y$（$y$是$x$的儿子），那么答案为$x$子树的贡献加$y$子树的贡献加$x$与$y$两两之间的贡献，即$dp1_x=dp1_x+dp1_y+\sum_{i\in tree(x)}\sum_{j\in tree(y)}dis(i,j)\times b_i\times b_j$。

把$dis(i,j)$拆开：

$$dp1_x=dp1_x+dp1_y+\sum_{i\in tree(x)}\sum_{j=\in tree(y)}(dis(i,x)+dis(x,y)+dis(y,j))\times b_i\times b_j\\=dp1_x+dp1_y+(\sum_{i\in tree(x)}dis(i,x)\times b_i)\times(\sum_{j\in tree(y)}b_j)+(\sum_{i\in tree(x)}b_i)\times(\sum_{j\in tree(y)}dis(y,j)\times b_j)+dis(x,y)\times(\sum{i\in tree(x)}b_i)\times(\sum_{j\in tree(y)}b_j)\\=dp1_x+dp1_y+dp2_x\times dp3_y+dp3_x\times dp2_y+dis(x,y)\times dp3_x\times dp3_y$$

$dp2$的转移和$dp3$的转移简单一些：

$$dp2_x=dp2_x+\sum_{i\in tree(y)}dis(i,x)\times b_i=dp2_x+\sum_{i\in tree(y)}(dis(x,y)+dis(i,y))\times b_i\\=dp2_x+dp2_y+\sum_{i\in tree(y)}dis(x,y)\times b_i=dp2_x+dp2_y+dp3_y\times dis(x,y)$$
$$dp3_x=dp3_x+dp3_y$$

最后的答案即为$dp1_1$。

由于建立虚树是$O(k\log k)$的，所以总复杂度为$O(n\log^2n)$

代码

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=200005,maxm=maxn<<1,mod=1000000007,maxk=25;
int n,e,cnt,ans,top,stp;
int a[maxn],start[maxn],to[maxm],then[maxm],f[maxn],P[maxn],p[maxn],pos[maxn],dfn[maxn],dep[maxn],fore[maxn][maxk],dp1[maxn],dp2[maxn],dp3[maxn],ok[maxn],stk[maxn],miu[maxn],phi[maxn],nphi[maxn];
vector<int>vp[maxn],g[maxn];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
inline void newadd(int x,int y){
    g[x].push_back(y);
}
inline int cmp(int a,int b){
    return dfn[a]<dfn[b];
}
void dfs(int x,int last){
    dfn[x]=++cnt,dep[x]=dep[last]+1,fore[x][0]=last;
    for(int i=1;i<=20;i++)
        fore[x][i]=fore[fore[x][i-1]][i-1];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])
        swap(a,b);
    for(int i=20;i>=0;i--)
        if(dep[fore[a][i]]>=dep[b])
            a=fore[a][i];
    if(a==b)
        return a;
    for(int i=20;i>=0;i--)
        if(fore[a][i]!=fore[b][i])
            a=fore[a][i],b=fore[b][i];
    return fore[a][0];
}
void DP(int x,int k){
    dp1[x]=dp2[x]=0,dp3[x]=a[x]%k==0? phi[a[x]]:0;
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i],z=(dep[y]-dep[x]+mod)%mod;
        DP(y,k);
        dp1[x]+=((dp1[y]+1ll*(dp2[x]+1ll*dp3[x]*z%mod)%mod*dp3[y])%mod+1ll*dp2[y]*dp3[x]%mod)%mod;
        dp2[x]+=(dp2[y]+1ll*dp3[y]*z%mod)%mod,dp3[x]+=dp3[y];
        dp1[x]%=mod,dp2[x]%=mod,dp3[x]%=mod;
    }
}
int calc(int k){
    top=0,stp++;
    for(int i=0;i<vp[k].size();i++)
        ok[vp[k][i]]=stp;
    sort(vp[k].begin(),vp[k].end(),cmp);
    g[1].clear(),stk[++top]=1;
    for(int i=0;i<vp[k].size();i++){
        if(vp[k][i]==1)
            continue;
        int l=lca(vp[k][i],stk[top]);
        if(l!=stk[top]){
            while(top>0&&dfn[l]<dfn[stk[top-1]])
                newadd(stk[top-1],stk[top]),top--;
            if(dfn[l]>dfn[stk[top-1]])
                g[l].clear(),newadd(l,stk[top]),top--,stk[++top]=l;
            else newadd(stk[top-1],stk[top]),top--;
        }
        g[vp[k][i]].clear(),stk[++top]=vp[k][i];
    }
    for(int j=1;j<top;j++)
        newadd(stk[j],stk[j+1]);
    DP(1,k);
    return dp1[1];
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
void sieve(){
    p[1]=phi[1]=miu[1]=nphi[1]=1;
    for(int i=2;i<=n;i++){
        if(p[i]==0)
            P[++cnt]=i,phi[i]=i-1,miu[i]=-1;
        for(int j=1;j<=cnt;j++){
            if(i*P[j]>n)
                break;
            p[i*P[j]]=1;
            if(i%P[j]==0){
                phi[i*P[j]]=phi[i]*P[j];
                miu[i*P[j]]=0;
                break;
            }
            phi[i*P[j]]=phi[i]*(P[j]-1);
            miu[i*P[j]]=-miu[i];
        }
        nphi[i]=ksm(phi[i],mod-2);
    }
}
int main(){
    scanf("%d",&n);
    sieve();
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        pos[a[i]]=i;
    }
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i){
            f[j]=(f[j]+1ll*i*miu[j/i]%mod*nphi[i]%mod)%mod;
            f[j]=(f[j]+mod)%mod;
        }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            vp[i].push_back(pos[j]);
    for(int i=1;i<=n;i++)
        ans+=2ll*f[i]*calc(i)%mod,ans%=mod;
    printf("%d\n",(int)(1ll*ans*ksm(n,mod-2)%mod*ksm(n-1,mod-2)%mod));
    return 0;
}

关于欧拉函数公式的证明

证明：

$$\varphi(n\times m)=\frac{\varphi(n)\times\varphi(m)\times\gcd(n,m)}{\varphi(\gcd(n,m))}$$
由欧拉函数的公式有：
$$\varphi(n\cdot m)\cdot\varphi(\gcd(n,m))=n\cdot m\cdot\prod_{p\mid n\cdot m,p\in\mathbb{P}}\frac{p-1}{p}\cdot\gcd(n,m)\cdot\prod_{q\mid\gcd(n,m),q\in\mathbb{P}}\frac{q-1}{q}\\=n\cdot m\cdot\prod_{p\mid lcm(n,m),p\in\mathbb{P}}\frac{p-1}{p}\cdot\prod_{q\mid\gcd(n,m),q\in\mathbb{P}}\frac{q-1}{q}\cdot\gcd(n,m)\\=n\cdot m\cdot\prod_{p\mid n或p\mid m,p\in\mathbb{P}}\frac{p-1}{p}\cdot\prod_{q\mid n且q\mid m,q\in\mathbb{P}}\frac{q-1}{q}\cdot\gcd(n,m)$$
我们根据容斥的思想可以得到：
$$\varphi(n\cdot m)\cdot\varphi(\gcd(n,m))=n\cdot\prod_{p\mid n,p\in\mathbb{P}}\frac{p-1}{p}\cdot m\cdot\prod_{q\mid m,q\in\mathbb{P}}\frac{q-1}{q}\cdot\gcd(n,m)\\=\varphi(n)\cdot\varphi(m)\cdot\gcd(n,m)$$