生成子群问题

· · 题解

orz 群论。

之前看到 grass8cow 博客中关于 Grupa Permutacji 这道题做法的简略记述后一直感觉这个题是究极神秘题。APIO 听了 Kubic 的讲课（当时讲的是 LOJ177 生成子群阶数）后终于算是懂了一点了。

众所周知，所有有限群同构于一个置换群的子群。当我们拿着一堆置换，然后再复合来复合去，所有可能得到的结果自然生成了一个群。grupa 这个题研究了这个群的平均逆序对个数，而 LOJ177 研究了这个群的大小。以前我一直认为这种东西很难做，出乎意料的是这两个问题都可以做到 O(\text{poly}(n))。

解决这两个问题的第一个共同关键是在于生成子群的“均匀性”。我们这样描述这个性质：对于所有置换的第 i 位 p_i 来说，假设 p_i 有 k 种不同的取值 a_1,a_2,\dots,a_k，则 p_i 取到这 k 种取值中的每种取值的方案数都是一样的。这个结论不仅对于单个 p_i 成立，对于多个 p_i 取值集合笛卡尔积形成的多元组来说也是成立的。

比如说，对于 grupa 这个题我们研究逆序对，所以对于一个下标二元组 (i,j)，生成子群中所有元素的取值二元组 (p_i,p_j) 取到每种可能的取值的概率相等。逆序对就是 i<j,p_i>p_j 的元组。所以我们直接对于每一个生成元排列的每一个二元组连双向边 (i,j)\leftrightarrow (p_i,p_j)，然后统计每个连通块中满足 i<j 和 i>j 的元组数，分别设为 a,b，则从每个 i<j 的元组出发到 i>j 的元组的概率是 \frac{b}{a+b}，对答案的总贡献就是 \frac{ab}{a+b}。我们得到了一个 O(n^3) 的做法。

如何说明这种“均匀性”呢？我们考虑建图分析。对于每个生成元置换 s 中若干个固定的下标形成的多元组 (\alpha_1,\alpha_2,\dots \alpha_m) 向 (s_{\alpha_1},s_{\alpha_2},\dots s_{\alpha_m}) 连边，再在这条边上写上 s 作为边权。

由于置换群不断的复合自己总会走回自己，所以说我们同时可以连一条反向边，再写上 s^{-1} 作为边权，所以我们可以直接将这张图当成无向图处理。不过就我们下面的分析来说有向图也没影响。

这样，你从任意元组 rt 开始 dfs，能 dfs 到的所有元组就是它能取到的所有取值元组。而你取任意一条路径 rt\to x，其上的所有边依次复合就得到了取到这个取值元组的一个置换。

我们不妨取一个以 rt 为根的 dfs 生成树。这样对于每一个 rt\to x 就钦定了唯一一条路径，那么对于一个取值元组取到 x 的方案，我们这条路径上的置换一一逆复合回去，由于置换群逆元存在且唯一，那么每一个取值元组取到 x 的置换一一对应着一个取值元组取到 rt 的置换。均匀性得证。

解决这两个问题第二个共同的关键在于如何削减生成元集合的大小，也就是说找到另一组生成元集合使得它们跟原生成元集合生成的群同构。如果你无聊中翻过 OI-wiki 中一些较为冷门的页面，你可能会知道 schreier-sims 算法 给出了一个这个问题的确定性做法。我没有认真看过这个算法 QwQ，只大致看过 Kubic APIO 讲义里的东西，但是更适合 OI 宝宝体质的做法是：随机选取一个生成元的子集，以任意顺序复合起来，重复足够多次之后将有大概率得到一些能够生成原来的群的置换。

所以对于 grupa 这个题我们选取 O(\log) 个子集后就得到了一个 O(n^2\log n) 的做法？！？！

// ...
int n,k;
int a[N][N];
int p[N],q[N];
inline int id(int x,int y){return (x-1)*n+y;}
int f[N*N],inv[N*N];
int ca[N*N],cb[N*N];
int rt(int x){
    if(f[x]==x) return x;
    return f[x]=rt(f[x]);
}
int main(){
    n=read();k=read();
    for(int i=1;i<=k;++i)
        for(int j=1;j<=n;++j) a[i][j]=read();
    for(int i=1;i<=n*n;++i) f[i]=i;
    for(int it=0;it<L;++it){
        for(int t=1;t<=n;++t) p[t]=t;
        for(int i=1;i<=k;++i)
            if(rng()&1){
                for(int t=1;t<=n;++t) q[p[t]]=a[i][t];
                for(int t=1;t<=n;++t) p[t]=q[t];
            }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                if(i==j) continue;
                f[rt(id(i,j))]=rt(id(p[i],p[j]));
            }
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            if(i==j) continue;
            if(i<j) ++ca[rt(id(i,j))];
            else ++cb[rt(id(i,j))];
        }
    inv[1]=1;
    for(int i=2;i<=n*n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
    int res=0;
    for(int i=1;i<=n*n;++i)
        if(f[i]==i&&ca[i]&&cb[i]) res=(res+(ll)ca[i]*cb[i]%P*inv[ca[i]+cb[i]])%P;
    printf("%d\n",res);
    return 0;
}

再考虑 LOJ177 这个题。我们统计有多少种置换，不妨先统计 p_n 有多少种取值，然后再统计强制 p_n=n 的方案数，两者相乘就是答案。

前者方法我们已经熟知，后者可以这样考虑：之前我们建出来的每一个经过 n 的环都是一个 p_n=n 的方案，我们有一组可以生成它们的生成元：对于每一条边 (u,v)，取 n\to u,u\to v,v\to n 这个环。对于这些生成元我们缩减它的集合大小至 O(n)，就可以递归到一个 n-1 的问题了！我们在 O(n^5) 的时间内解决了 LOJ177。

// ... const int B >= O(n);
struct perm{
    int p[N];
    void init(){
        for(int i=1;i<=n;++i) p[i]=i;
    }
    friend perm operator+(const perm a,const perm b){
        perm c;
        for(int i=1;i<=n;++i) c.p[i]=b.p[a.p[i]];
        return c;
    }
    perm inv(){
        perm x;
        for(int i=1;i<=n;++i) x.p[p[i]]=i;
        return x;
    }
}a[N],b[N],path[N<<1];
vector<pii> vec[N];
ll res[10];int len;
bool vis[N];
void dfs(int u,perm cur){
    path[u]=cur;
    vis[u]=1;++num;
    for(auto [v,w]:vec[u]){
        if(vis[v]) continue;
        dfs(v,cur+a[w]);
    }
}
void iter(){
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j) vec[j].emplace_back(a[i].p[j],i);
    perm Init;
    Init.init();
    dfs(n,Init);
    for(int i=1;i<=n;++i) path[i+n]=path[i].inv(),vec[i].clear();
    for(int it=1;it<=B;++it){
        b[it].init();
        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j)
                if(vis[j]&&(rng()&1)) b[it]=b[it]+path[j]+a[i]+path[a[i].p[j]+n];
    }
    for(int i=1;i<=n;++i) vis[i]=0;
    m=B;
    for(int i=1;i<=m;++i) a[i]=b[i];
    --n;
    ll carry=0;
    for(int i=0;i<=len;++i){
        res[i]*=num;res[i]+=carry;
        carry=res[i]/T;res[i]%=T;
    }
    if(carry) res[++len]=carry;
    num=0;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j) a[i].p[j]=read();
    res[len=0]=1;
    while(n) iter();
    printf("%lld",res[len]);
    for(int i=len-1;~i;--i) printf("%016lld",res[i]);
    putchar('\n');
    return 0;
}

upd:

拜谢环一周！在与环一周讨论后我们弄明白了这样一个问题：

对于一个群，我们求其最少生成元个数，称为这个群的秩。

一个群的秩是可以达到 O(n) 级别的，构造一些二元环即可顶到这个界。

所以说求群阶数时一定要保留 O(n) 级别的生成元。

但 grupa 那个题只需要你把生成元连成的图连出来，这时候不需要遍历到所有生成元就可以建出这张图了，所以只需要保留 O(\log n) 级别的生成元。