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