O(nq) 100Pts题解

放上证明，CCF数据真的是水

我们设 $ans[i]$ 表示以 $i$ 为根的堆，填入 $size[i]$ 个数字，总的方案数。

那么我们每次 menge 的时候，假设将 $root1$ menge 到 $root2$ 上面，每次令 $ans[root2]=1$ 。

然后枚举 $root2$ 的所有儿子，相当于把 $size[root2]$ 分成 $son\_num[root2]$ 份，结合 $size[son]$ 就可以计算 $ans[root2]$ 了。

这里用到了一些组合数，也不是很难。

这样的算法在菊花图里是要被卡成 $O(nq)$ 的，因为每次 menge 都会重新计算一遍 $size[root2]$ 。

这份自带大常数、应该 $50 pts$ 的代码，它A了......

附上考场代码，（线性求逆元都没用，也没想到能A）：

//heap.cpp

#include<bits/stdc++.h>
using namespace std;
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<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

const int N=3e5+5,mod=1e9+7;

vector<int>son[N];

int fa[N],siz[N],n,q;

long long ans[N];
long long lastans;

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

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

int fac[N];

inline long long C(int x,int y){
    return 1ll*(1ll*fac[y]*ksm(fac[x],mod-2)%mod)*(ksm(fac[y-x],mod-2))%mod;
}

void Menge(int x,int y){
    int root1=find(x),root2=find(y);
    fa[root1]=root2;
    son[root2].push_back(root1);
    siz[root2]+=siz[root1];
    int used=1;
    ans[root2]=1;
    for(int i=0;i<son[root2].size();i++){
        ans[root2]=(1ll*ans[root2]*ans[son[root2][i]]%mod * C(siz[son[root2][i]],siz[root2]-used))%mod;
    //  cerr<<ans[1]<<endl;
    //  cerr<<"ans[root2]="<<ans[root2]<<endl;
    //  cerr <<"ans[root2]*= C( "<<siz[son[root2][i]]<<" , "<<siz[root2]-used<<endl;
        used+=siz[son[root2][i]];

    }
    //cerr<<"menged" <<x<<" "<<y<<endl;
    //cerr<<"size[root1]="<<siz[root1]<<"  size[root2]="<<siz[root2]<<endl;
}

int main(){
freopen("heap.in","r",stdin);
freopen("heap.out","w",stdout);
    n=read();
    q=read();
    fac[1]=1;
    fac[0]=1;
    for(int i=2;i<=n;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    //  cout<<C(1,1)<<endl;
    memset(fa,-1,sizeof fa);
    for(int i=0;i<=n;i++)
        siz[i]=1,fa[i]=i,ans[i]=1;
    while(q--){
        int opt,x,y;
        opt=read();
        if(opt==1){
            x=read(),y=read();
            x=(x+lastans)%n;
            y=(y+lastans)%n;
            //cout<<"x="<<x<<"y="<<y<<endl;
            Menge(x,y);
        }
        else if(opt==2){
            x=read();
            x=(x+lastans)%n;
            printf("%lld\n",ans[find(x)]);
            lastans=ans[find(x)];
        }
    }
    return 0;
}