CF809E题解

给定一个排列 \(a_i\) 和一棵树，求：

\[\frac 1 {n(n-1)}\sum_{i=1}^n\sum_{j=1}^n \varphi(a_i \times a_j) \times dis(i,j) \]

因为 \(a\) 是一个排列，我们考虑对其求逆。
设 \(p_{a_i}=i\)，则有：

\[\sum_{i=1}^n\sum_{j=1}^n\varphi(ij) \times dis(p_i,p_j) \]

众所周知有 \(\varphi(nm)=\frac {\varphi(n)\varphi(m)\gcd(n,m)} {\varphi(\gcd(n,m))}\)

\[\sum_{i=1}^n\sum_{j=1}^n\frac {\varphi(i)\varphi(j)\gcd(i,j)} {\varphi(\gcd(i,j))} \times dis(p_i,p_j) \]

接下来就全是套路了。

\[\sum_{d=1}^n\frac d {\varphi(d)}\sum_{i=1}^n\sum_{j=1}^n\varphi(i)\varphi(j)dis(p_i,p_j)[\gcd(i,j)=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}\varphi(id)\varphi(jd)dis(p_i,p_j)\sum_{x|i,x|j}\mu(x) \]

\[\sum_{d=1}^n\frac d {\varphi(d)}\sum_{x=1}^{\lfloor \frac n d \rfloor}\mu(x)\sum_{i=1}^{\lfloor \frac n {dx} \rfloor}\sum_{j=1}^{\lfloor \frac n {dx} \rfloor}\varphi(idx)\varphi(jdx)dis(p_i,p_j) \]

\[\sum_{T=1}^n(\frac {id} {\varphi} * \mu)(T)\sum_{i=1}^{\lfloor \frac n T \rfloor}\sum_{j=1}^{\lfloor \frac n T \rfloor}\varphi(iT)\varphi(jT) \times dis(p_i,p_j) \]

于是枚举 \(T\)，枚举 \(T\) 的倍数，对其节点建立虚树，然后统计答案。

\[\varphi(i)\varphi(j)(d_{p_i}+d_{p_j}-2 \times d_{lca(p_i,p_j)}) \]

前面的部分可以 \(O(n)\) 计算，后面的在 \(LCA\) 处统计贡献就行了。

复杂度应该是 \(O(n\log^2n)\) 的。

对 \(O(n\log n)\) 的瞎 yy

在 DFS 的时候，对虚树的序列直接插入点即可。

枚举因数随便预处理一下就 \(O(n\log n)\) 了。

以下是卡常 114514 次后的代码。因为常数问题最后还是选择了树剖LCA

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("no-stack-protector")
#include
#include
#include
typedef unsigned ui;
const ui M=2e5+5,mod=1e9+7;
ui n,m,cnt,a[M],p[M],h[M],V[M],F[M],phi[M],pos[M];ui Top,pri[M];ui d[M],f[M],siz[M],son[M],top[M];
ui sum,ans;ui tp,stk[M];char buf[1<<21|1],*Jerry=buf;ui L[M],l[M],f1[M*19],f2[M*19],*G[M],*fac[M],*now1=f1,*now2=f2;
inline char Getchar(){
	return*Jerry=='\0'&&std::cin.read(Jerry=buf,1<<21),*Jerry++;
}
inline ui read(){
	ui n(0);char s;while(!isdigit(s=Getchar()));while(n=n*10+(s&15),isdigit(s=Getchar()));return n;
}
struct Edge{
	ui v,nx;
}e[M<<1];
inline void Add(const ui&u,const ui&v){
	e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
}
inline ui pow(ui a,ui b){
	ui ans(1);
	for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;
	return ans;
}
void DFS1(const ui&u){
	d[u]=d[f[u]]+1;siz[u]=1;
	for(ui v,E=h[u];E;E=e[E].nx)if((v=e[E].v)^f[u]){
		f[v]=u;DFS1(v);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void DFS2(const ui&u,const ui&tp){
	ui*g=fac[a[u]];top[u]=tp;for(ui x=0;x^L[a[u]];++x)if(F[g[x]])G[g[x]][l[g[x]]++]=a[u];
	if(!son[u])return;DFS2(son[u],tp);for(ui E=h[u];E;E=e[E].nx)if(e[E].v^f[u]&&e[E].v^son[u])DFS2(e[E].v,e[E].v);
}
inline ui LCA(ui u,ui v){
	while(top[u]^top[v]){
		if(d[top[u]]>d[top[v]])u=f[top[u]];
		else v=f[top[v]];
	}
	return d[u]>d[v]?v:u;
}
void Solve(const ui&u){
	for(ui v,E=h[u];E;E=e[E].nx){
		Solve(v=e[E].v);sum=(sum+2ull*V[u]*V[v]%mod*(mod-d[u]))%mod;V[u]=(V[u]+V[v])%mod;h[v]=V[v]=0;
	}
	if(u==1)h[u]=V[u]=0;
}
inline void Insert(const ui&u){
	const ui&v=LCA(u,stk[tp]);while(tp^1&&d[stk[tp-1]]>d[v])Add(stk[tp-1],stk[tp]),--tp;
	if(stk[tp]^v)Add(v,stk[tp--]);if(stk[tp]^v||!tp)stk[++tp]=v;if(stk[tp]^u)stk[++tp]=u;
}
inline void calc(const ui&x){
	ui S(0),*g=G[x];stk[tp=1]=1;cnt=sum=0;
	for(ui u=0;u^l[x];++u)S=(S+phi[g[u]])%mod,Insert(p[g[u]]),V[p[g[u]]]=phi[g[u]];
	while(tp^1)Add(stk[tp-1],stk[tp]),--tp;
	for(ui u=0;u^l[x];++u)sum=(sum+1ull*(S+mod-phi[g[u]])*d[p[g[u]]]%mod*phi[g[u]])%mod;
	Solve(1);ans=(ans+2ull*sum*F[x])%mod;
}
inline void sieve(){
	ui i,j,x;F[1]=phi[1]=1;
	for(i=2;i<=n;++i){
		if(!pos[i])pri[pos[i]=++Top]=i,F[i]=pow(phi[i]=i-1,mod-2);
		for(j=1;j<=pos[i]&&(x=i*pri[j])<=n;++j){
			pos[x]=j;phi[x]=j==pos[i]?phi[i]*pri[j]:phi[i]*phi[pri[j]];
			F[x]=j==pos[i]?0:1ull*F[i]*F[pri[j]]%mod;
		}
	}
	for(i=1;i<=n;++i)for(j=1;(x=i*j)<=n;++j)++L[x];
	for(i=1;i<=n;++i)G[i]=now1,now1+=n/i,fac[i]=now2,now2+=L[i];
	for(i=1;i<=n;++i)for(j=1;(x=i*j)<=n;++j)fac[x][--L[x]]=i;
	for(i=1;i