mcfx's blog

题解、Writeup、游记和碎碎念

Codeforces 809E. Surprise me!

给一棵树,每个点点权 aia_i,保证 aia_i 各不相同,现在随机选两个点 u,vu,v,求 f(u,v)=φ(auav)dis(u,v)f(u,v)=\varphi(a_u\cdot a_v)\cdot dis(u,v) 的期望,mod109+7\bmod 10^9+7

链接:http://codeforces.com/contest/809/problem/E

Solution

首先,有一个结论:φ(ab)=φ(a)φ(b)gφ(g),g=gcd(a,b)\varphi(a\cdot b)=\frac{\varphi(a)\cdot\varphi(b)\cdot g}{\varphi(g)},g=\gcd(a,b)
证明:考虑找一个 xx,使得 xb,gcd(bx,a)=1,gcd(x,bx)=1x|b,\gcd(\frac{b}{x},a)=1,\gcd(x,\frac{b}{x})=1aa 包含 xx 中所有质因子。
那么 φ(ab)=φ(a)xφ(bx)=φ(a)φ(b)xφ(x)\varphi(a\cdot b)=\varphi(a)\cdot x\cdot\varphi(\frac{b}{x})=\frac{\varphi(a)\cdot\varphi(b)\cdot x}{\varphi(x)}
显然,xxgg 的倍数,所以 xg=φ(x)φ(g)\frac{x}{g}=\frac{\varphi(x)}{\varphi(g)},所以 φ(ab)=φ(a)φ(b)gφ(g)\varphi(a\cdot b)=\frac{\varphi(a)\cdot\varphi(b)\cdot g}{\varphi(g)}

有了这个结论之后可以考虑点分,那么设 dis(x)dis(x) 表示 xx 到当前根的距离。
h(x)=xφ(x)h(x)=\frac{x}{\varphi(x)},那么 f(u,v)=φ(au)φ(av)h(g)(dis(u)+dis(v)),g=gcd(au,av)f(u,v)=\varphi(a_u)\cdot\varphi(a_v)\cdot h(g)\cdot(dis(u)+dis(v)),g=\gcd(a_u,a_v)
考虑当 uu 确定时,需要知道 φ(av)h(gcd(au,av))\sum\varphi(a_v)\cdot h(\gcd(a_u,a_v))φ(av)h(gcd(au,av))dis(v)\sum\varphi(a_v)\cdot h(gcd(a_u,a_v))\cdot dis(v)
g(x)=h(x)[yx,yx]g(y)g(x)=h(x)-\sum[y|x,y\neq x]g(y),那么 h(gcd(au,av))=[xau,xav]g(x)h(\gcd(a_u,a_v))=\sum[x|a_u,x|a_v]g(x)
这样就可以直接枚举约数算贡献了。

Code

#include<bits/stdc++.h>
typedef long long ll;
inline void repr(int&a,int b){if(a<b)a=b;}
#define mset(a,b) memset(a,b,sizeof(a))
#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define foe(i,x)for(__typeof(x.end())i=x.begin();i!=x.end();++i)

const int N=200007,P=1000000007;

struct edge
{
    int to;edge*ne;
}_e[N*2],*e=_e,*p[N];

inline void add(int a,int b)
{
    *e=(edge){b,p[a]};p[a]=e++;
}

std::vector<int>v[N];
int n,pr[N],pm,phi[N],inv[N],f[N],w[N],sz[N],rsz,nro,nsz,g[N],h[N],q[N],qe,ans;
bool vis[N];

inline void dfs1(int x,int fa)
{
    sz[x]=1;
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
        {
            dfs1(i->to,x);
            sz[x]+=sz[i->to];
        }
}

inline void dfs2(int x,int fa)
{
    int t=rsz-sz[x];
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
        {
            repr(t,sz[i->to]);
            dfs2(i->to,x);
        }
    if(t<nsz)nsz=t,nro=x;
}

inline void set(int x,int y,int z)
{
    if(!~g[x])q[qe++]=x,g[x]=h[x]=0;
    g[x]=(g[x]+(ll)y*f[x])%P;
    h[x]=(h[x]+(ll)z*f[x])%P;
}

inline void get(int x,int&y,int&z)
{
    if(~g[x])y=g[x],z=h[x];
    else y=z=0;
}

inline void dfs3(int x,int fa,int dis)
{
    int a=phi[w[x]],b=(ll)a*dis%P;
    foe(i,v[w[x]])set(*i,a,b);
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
            dfs3(i->to,x,dis+1);
}

inline void dfs4(int x,int fa,int dis)
{
    int a=phi[w[x]],b=(ll)a*dis%P,A,B;
    foe(i,v[w[x]])
    {
        get(*i,A,B);
        ans=(ans+(ll)a*B+(ll)b*A)%P;
    }
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
            dfs4(i->to,x,dis+1);
}

inline void work(int x)
{
    dfs1(x,0);
    rsz=nsz=sz[x],nro=x;
    dfs2(x,0);
    vis[x=nro]=1;
    foe(i,v[w[x]])set(*i,phi[w[x]],0);
    for(edge*i=p[x];i;i=i->ne)
        if(!vis[i->to])
        {
            dfs4(i->to,x,1);
            dfs3(i->to,x,1);
        }
    fo0(i,qe)g[q[i]]=h[q[i]]=-1;
    qe=0;
    for(edge*i=p[x];i;i=i->ne)
        if(!vis[i->to])work(i->to);
}

int main()
{
    fo1(i,N-1)for(int j=i;j<N;j+=i)v[j].push_back(i);
    fo(i,2,N-1)
    {
        if(!vis[i])pr[pm++]=i,phi[i]=i-1;
        for(int j=0;i*pr[j]<N;j++)
        {
            vis[i*pr[j]]=1;
            if(i%pr[j]==0)
            {
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
            phi[i*pr[j]]=phi[i]*(pr[j]-1);
        }
    }
    phi[1]=1;
    inv[1]=1;
    fo(i,2,N-1)inv[i]=(ll)(P-P/i)*inv[P%i]%P;
    fo1(i,N-1)
    {
        f[i]=(ll)i*inv[phi[i]]%P;
        foe(j,v[i])if(i^*j)(f[i]+=P-f[*j])%=P;
    }
    scanf("%d",&n);
    fo1(i,n)scanf("%d",w+i);
    fo0(i,n-1)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    mset(vis,0);
    mset(g,0xff);
    mset(h,0xff);
    work(1);
    ans=(ll)ans*inv[n]%P*inv[n-1]%P*2%P;
    printf("%d",ans);
}

日期: 2017-05-25

标签: Codeforces 数论 点分治

这是一篇旧文,原始文章及评论可在 https://oldblog.mcfx.us/archives/236/ 查看。