6.1 NOI 模拟

\(T1\ pocky\)

要求式子

\[\sum_{i=2}^n a_i\times \gcd(a_i,a_{i-1})
\]

考虑可以枚举\(a_i,a_{i-1}\)的值,然后插板法,枚举每个位置的情况然后单独统计贡献,复杂度\(O(n\times m^2)\)

有了\(\gcd\)大概就和\(\mu\)有些关系了

\[Ans=\sum_{i,j}\gcd(i,j) \times i\times \binom{n-i-j-1}{m-3}
\]

我们把序列先拿出\(id+jd\)部分,然后其余的位置隔板法

\[\sum_{i=1}^n i\sum_{j=1}^n \gcd(i,j)\binom{n-i-j}{m-3}
\\
\sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}i\times d\sum_{j=1}^{\frac{n}{d}}d\binom{n-i\times d-j\times d-1}{m-3}[\gcd(i,j)==1]
\\
\sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}i\times d\sum_{j=1}^{\frac{n}{d}}d\binom{n-i\times d-j\times d-1}{m-3}\sum_{p|i,p|j}\mu(p)
\\
\sum_{d=1}^n\sum_{p=1}^{\frac{n}{d}}\mu(p)\sum_{i=1}^{\frac{n}{dp}}i\times d\times p\sum_{j=1}^{\frac{n}{dp}}d\binom{n-i\times d\times p-j\times d\times p-1}{m-3}
\\
\sum_{q=1}^n\sum_{p|q}\mu(p)\sum_{i=1}^{\frac{n}{q}}i\times q\sum_{j=1}^{\frac{n}{q}}\frac{q}{p}\binom{n-i\times q-j\times q-1}{m-3}
\\
\sum_{q=1}^n\sum_{p|q}\frac{q}{p}\mu(p)\sum_{i=1}^{\frac{n}{q}}i\times q\sum_{j=1}^{\frac{n}{q}}\binom{n-i\times q-j\times q-1}{m-3}
\\
\sum_{q=1}^n\sum_{i=1}^{\frac{n}{q}}i\times q\sum_{j=1}^{\frac{n}{q}}\binom{n-i\times q-j\times q-1}{m-3}(\mu*id)(q)
\\
\sum_{q=1}^n\varphi(q)\sum_{i=1}^{\frac{n}{q}}i\times q\sum_{j=1}^{\frac{n}{q}}\binom{n-i\times q-j\times q-1}{m-3}
\]

先看式子的后半部分

\[\sum_{i=1}^{\frac{n}{q}}i\times q\sum_{j=1}^{\frac{n}{q}}\binom{n-i\times q-j\times q-1}{m-3}
\\
q\times \sum_{k=1}^{\frac{n}{q}}\binom{n-k\times q -1}{m-3}\frac{k\times(k-1)}{2}
\]

反代回去

\[\frac{1}{2}\sum_{q=1}^{n}\varphi(q)q\sum_{k=1}^{\frac{n}{q}}\binom{n-k\times q-1}{m-3}k\times(k-1)
\\
\frac{1}{2}\sum_{x=1}^{n}\binom{n-x-1}{m-3}x\sum_{q|x}\varphi(q)(\frac{x}{q}-1)
\\
\frac{1}{2}\sum_{x=1}^n\binom{n-x-1}{m-3}x\huge(\small \sum_{q|x}\varphi(q)\frac{x}{q}\large-(\varphi*I)(x)\huge)
\\
\frac{1}{2}\sum_{x=1}^n\binom{n-x-1}{m-3}x\huge(\small \sum_{q|x}\varphi(q)\frac{x}{q}\large-x\huge)
\\
\frac{1}{2}\sum_{x=1}^n\binom{n-x-1}{m-3}x \sum_{q|x}\varphi(q)\frac{x}{q}\large-
\frac{1}{2}\sum_{x=1}^n\binom{n-x-1}{m-3}x^2
\]

最后那个东西可以\(O(n)\)预处理,最终复杂度\(O(n)\)

\(qs\)很\(nb\)

#define Eternal_Battle ZXK

#include<bits/stdc++.h>

#define mod 1000000007

#define MAXN 10000005

using namespace std;

int n,m;

long long res;

int fac[MAXN],invjc[MAXN],invs[MAXN];

int my_pow(int x,int y)

{

    int res=1;

    while(y)

    {

        if(y&1) res=1ll*res*x%mod;

        x=1ll*x*x%mod;

        y=(y>>1);

    }

    return res;

}

int inv(int x)

{

    return my_pow(x,mod-2);

}

int C(int n,int m)

{

    if(n<m) return 0;

    return 1ll*fac[n]*invjc[m]%mod*invjc[n-m]%mod;

}

bitset<MAXN> sh;

int pri[1000001],cnt,phi1[MAXN];

struct que

{

    int mini,mnum,msy;

}s[MAXN];

int init(int n,int x,int k)

{

    return 1ll*n*(1+1ll*k*(x-1)%mod*invs[x]%mod)%mod;

}

void init(int n)

{

    phi1[1]=1;

    s[1].mini=1,s[1].mnum=0;

    for(int i=2;i<=n;++i)

    {

        if(!sh[i])

        {

            pri[++cnt]=i;

            s[i]={i,1,i};

        }

        for(int j=1,v;j<=cnt&&i<=n/pri[j];++j)

        {

            v=i*pri[j];

            sh[v]=1;

            if(i%pri[j]==0)

            {

                s[v]={s[i].mini,s[i].mnum+1,pri[j]*s[i].msy};

                break;

            }

            s[v]={pri[j],1,pri[j]};

        }

    }

    for(int i=2;i<=n;++i)

    {

        if(s[i].msy==i) phi1[i]=init(s[i].msy,s[i].mini,s[i].mnum);

        else phi1[i]=1ll*phi1[i/s[i].msy]*phi1[s[i].msy]%mod;

    }

}

signed main()

{

    scanf("%d %d",&n,&m);

    fac[0]=1;

    for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;

    invjc[n]=inv(fac[n]);

    for(int i=n-1;i>=0;--i) invjc[i]=1ll*invjc[i+1]*(i+1)%mod;

    for(int i=n;i>=1;--i) invs[i]=1ll*invjc[i]*fac[i-1]%mod;

    init(n);

    for(int i=1;i<=n;++i) res+=1ll*i*C(n-i-1,m-3)%mod*(phi1[i]%mod-i)%mod;

    res=res%mod*inv(2)%mod;

    res=res*(m-1)%mod;

    res=(res+mod)%mod;

    cout<<res;

}

\(T2\ station\)

动态的,无法离线的,不能预处理的,复杂度可以保证的,所以是这道题是点分树的

还是考虑如何计算贡献

考虑建出点分树

首先考虑贡献的计算方式吧

\[val_{x\rightarrow y}=\frac{1}{deg[x]}\Pi_{poi\in rd(x\rightarrow y),poi\ne x,poi\ne y}\frac{1}{deg[poi]-1}
\]

\(x\rightarrow y\)有贡献当且仅当\(Dist(x,y)\leq dis\)

我们考虑在点分树的每一个节点维护一个树状数组,我们每次在对应深度插入,查询的时候询问大于等于的一段区间的和,后半部分可以直接预处理到节点的距离和贡献

#include<bits/stdc++.h>

#define int long long

#define mode 998244353

#define N 300011

#define M 23

using namespace std;

int n,m,invs[N],deg[N];

vector<int> road[N];

int poww(int x,int y)

{

    int res=1;

    while(y)

    {

        if(y&1) res=res*x%mode;

        x=x*x%mode;

        y=(y>>1);

    }

    return res;

}

int inv(int x)

{

    return poww(x,mode-2);

}

struct tree{

    int n;

    vector <int> s;

    tree(){};

    tree(int n):n(n){ s.resize(n+1); }

    void add(int p,int x)

    {

        p=min(p,n);

        while(p)

        {

            (s[p]+=x)%=mode;

            p-=p&-p;

        }

    }

    int query(int p)

    {

        int res=0;

        while(p<=n)

        {

            (res+=s[p])%=mode;

            p+=p&-p;

        }

        return res;

    }

}T[N];

vector<tree>tr[N];

int Dep[N],pos[M][N],dep[M][N],s[M][N],vis[N],siz[N],fa[N],root;

int mi,rt,nowd,maxd,all;

void find_root(int x,int f)

{

    int ma=0;

    siz[x]=1;

    for(int i=0;i<road[x].size();++i)

    if(road[x][i]!=f&&!vis[road[x][i]])

    {

        find_root(road[x][i],x);

        siz[x]+=siz[road[x][i]];

        ma=max(ma,siz[road[x][i]]);

    }

    ma=max(ma,all-siz[x]);

    if(mi>ma) mi=ma,rt=x;

}

void dfs(int x,int f,int id)

{

    maxd=max(maxd,dep[nowd][x]=dep[nowd][f]+1);

    pos[nowd][x]=id;

    for(int i=0;i<road[x].size();++i)

    if(road[x][i]!=f&&!vis[road[x][i]])

    {

        s[nowd][road[x][i]]=1ll*s[nowd][x]*invs[deg[x]-1]%mode;

        dfs(road[x][i],x,id);

    }

}

int solve(int x)

{

    mi=1e9;

    find_root(x,x);

    x=rt;

    vis[x]=1;

    s[Dep[x]=nowd][x]=1,pos[nowd][x]=-1;

    int t=0,cnt=0;

    for(int i=0;i<road[x].size();++i)

    if(!vis[road[x][i]])

    {

        maxd=0;

        s[nowd][road[x][i]]=1;

        dfs(road[x][i],x,cnt);

        tr[x].push_back(tree(maxd));

        t=max(t,maxd);

        ++cnt;

    }

    T[x]=tree(t);

    int tmp=all;

    for(int i=0;i<road[x].size();++i)

    if(!vis[road[x][i]])

    {

        if(siz[road[x][i]]>siz[x])

        siz[road[x][i]]=tmp-siz[x];

        nowd++;

        all=siz[road[x][i]];

        fa[solve(road[x][i])]=x;

        nowd--;

    }

    return x;

}

int sum[N];

int query(int x)

{

    int ans=sum[x];

    for(int v=x,d=Dep[v];(d--,v=fa[v]);) ans=(ans+(T[v].query(dep[d][x])+tr[v][pos[d][x]].query(dep[d][x]))*s[d][x])%mode;

    return (ans%mode+mode)%mode;

}

void change(int x,int d)

{

    sum[x]++;

    (sum[x])%=mode;

    T[x].add(d,invs[deg[x]]);

    for(int v=fa[x],nowd=Dep[x]-1;v;v=fa[v],nowd--)

    {

        if(d<dep[nowd][x]) continue;

        int t=1ll*invs[deg[x]]*s[nowd][x]%mode;

        (sum[v]+=t)%=mode;

        t=t*invs[deg[v]-1]%mode;

        T[v].add(d-dep[nowd][x],t),tr[v][pos[nowd][x]].add(d-dep[nowd][x],mode-t);

    }

}

inline int read(){

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')

            f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9'){

        x=(x<<1)+(x<<3)+(ch^48);

        ch=getchar();

    }

    return x*f;

}

int lst;

signed main()

{

    n=read(),m=read();

    for(int i=1;i<=n;++i) invs[i]=inv(i);

    for(int i=2,u,v;i<=n;++i)

    {

        u=read(),v=read();

        road[u].push_back(v);

        road[v].push_back(u);

        deg[u]++,deg[v]++;

    }

    all=n;

    root=solve(1);

    for(int i=1,opt,x,d;i<=m;++i)

    {

        opt=read();

        if(opt==1)

        {

            x=read(),d=read();

            x=(x+lst)%n+1;

            d=(d+lst)%n+1;

            change(x,d);

        }

        else

        {

            x=read();

            x=(x+lst)%n+1;

            printf("%lld\n",lst=query(x));

        }

    }

}

\(T3\ game\)

6.1 NOI 模拟的相关教程结束。