设 \(f_u\) 表示以 \(u\) 为根的子树构成不同多叉堆的方案数。显然最小的 \(0\) 应该分配给 \(u\)，剩下的分给子节点 \(v_1,v_2,\cdots,v_k\)，根据乘法原理，有
\[f_u=\prod_{i=1}^k \binom{siz_u-1-\sum_{j=1}^{i-1}siz_{v_j}}{siz_{v_i}}f_{v_i}
\]
将组合数和 \(f\) 分开，观察到组合数全部乘起来后分子即为 \((siz_u-1)!\)，分母即为子节点大小阶乘的乘积，即
\[f_u=\dfrac{(siz_u-1)!}{\prod_{i=1}^ksiz_{v_i}!}\prod_{i=1}^kf_{v_i}
\]
直接使用并查集维护点的关系，并在合并时更新对应的 \(f\) 即可。使用快速幂计算逆元，时间复杂度 \(O(n\log n+q)\)。
#include<iostream>
#include<cstdio>
#define N 500010
#define mod 1000000007
#define int long long
using namespace std;
int n,m,fa[N],f[N],fac[N],inv[N],siz[N],ans;
int qp(int a,int b){int c=1;while(b){if(b&1)c=c*a%mod;b>>=1;a=a*a%mod;}return c;
}
int cx(int x){if(x==fa[x])return x;return fa[x]=cx(fa[x]);
}
signed main(){//f[u]=C_{siz[u]-1}^siz[v1]*f[v1]*C_{siz[u]-siz[v1]-1}^siz[v2]*f[v2]......*C_{siz[vk]}^siz[vk]*f[vk];// =(siz[u]-1)!/(siz[v1]!siz[v2]!...siz[vk]!)*f[v1]f[v2]...f[vk]int op,x,y;cin>>n>>m;fac[0]=inv[0]=1;for(int i=1;i<=n;i++){fac[i]=fac[i-1]*i%mod;inv[i]=qp(fac[i],mod-2);fa[i]=i,siz[i]=1,f[i]=1;}while(m--){cin>>op;if(op==1){cin>>x>>y;x=(x+ans)%n;y=(y+ans)%n;x++;y++;x=cx(x),y=cx(y);f[y]=f[y]*inv[siz[y]-1]%mod*fac[siz[y]+siz[x]-1]%mod;f[y]=f[y]*inv[siz[x]]%mod;f[y]=f[y]*f[x]%mod;fa[x]=y;siz[y]+=siz[x];}if(op==2){cin>>x;x=(x+ans)%n;x++;x=cx(x);ans=f[x];cout<<ans<<'\n';}}return 0;
}
)
底层原理详解)
)
)
