ZJT's Blog

大変に気分がいい~

有限交换群的分解算法

2018-9-13 13:142018-10-26 14:20
群论抽象代数

众所周知(?),有限交换群(即有限阿贝尔群)可被分解为若干个质数幂阶循环群的直积。然而沙雕zjt之前一直不知道怎么求出这个分解,最近看了LCA的论文和几篇paper,稍微学习了一个,这里就总结一下吧。

前置知识

有限阿贝尔群基本定理:所有有限阿贝尔群都可以被表示成若干质数幂阶循环子群的直积。(证明naidesu)

Sylow p-子群:现有任意有限群$G$及质数$p$,令$p^k$为能整除$|G|$的最高次幂,则$G$存在阶为$p^k$的子群,称为$G$的Sylow p-子群。在有限交换群中,$G$可以被分解为各个Sylow p-子群的直积。

记$\langle x\rangle$为$x$生成的循环子群,$|\langle x\rangle|$称为$x$的阶,记作$|x|$。以下内容都在某个有限交换群$G$中进行。记$n=|G|$。

线性无关:称$\{b_1,b_2,\cdots,b_k\}$线性无关,当且仅当对于任意$i$,有$\langle b_i\rangle\cap\prod_{j\ne i}\langle b_j\rangle=\{e\}$。若不满足则称为线性相关。元素$x$与集合$A$线性无关的定义类似,即$\{x\}\cup A$线性无关。

基(basis):称$\{b_1,b_2,\cdots,b_k\}$为$G$的一组基,当且仅当$\prod \langle b_i\rangle=G$,且$b_1,b_2,\cdots,b_k$线性无关。

我们要实现的事情是求出$G$的直积分解,并给出对应的基。由于在非交互题中给出整个群就已经是$O(n^2)$的了,这里先介绍一个$O(n^2)$的算法。事实上还存在着复杂度更低甚至线性的算法,这里先咕着(

算法介绍

我们先考虑只有一个Sylow p-子群的情况,即$|G|=p^k$。首先可以$O(n^2)$求出每个元素的阶(这显然不是复杂度下界,不过更低也没啥意义)。算法的基本思路是按照阶从大到小求出每个基,在求的过程中维护与当前基线性相关的元素集合,然后在剩下的集合里选出新的基。

记当前基的集合为$B$,$L$为$B$生成的子群,$M$为所有跟当前基线性相关的元素集合。我们有引理:对于$x\in M,x\notin L$,且$|x|\leq\min_{b\in B}|b|$,一定可以找到$x'\notin M$,使得$\prod_{b\in B\cup{\{x\}}}\langle b\rangle=\prod_{b\in B\cup{\{x'\}}}\langle b\rangle$,且$|x'|\big||x|$。

这个引理说明了,我们贪心在$G\setminus M$中选取阶最大的元素,不会产生$L\ne G$却找不到新的基的情况,即证明了该算法的正确性。

当$G$含有多个Sylow p-子群的情况呢?事实上这个算法依然是对的,因为每个Sylow p-子群内部发生的事情实际上可以看作是独立的,我们每次找出阶最大的元素其实等价于在每个Sylow p-子群内都找出一个阶最大的元素。我们在找出最大阶元素的同时对阶进行一下质因数分解,求出每个Sylow p-子群对应的基即可。

整理一下算法的具体流程:

  1. 求出每个元素的阶
  2. 维护$B,L,M$,初始时$B=\varnothing,L=M=\{e\}$
  3. 在$G\setminus M$中找到阶最大的元素$g$,对$|g|$进行质因数分解,求出每个Sylow p-子群对应的基$g_{p_1},g_{p_2},\cdots$,并加入$B$中
  4. 每当$B$中插入新的基,枚举原有的$L$进行运算,扩展出新的$L$(设新插入的基为$b$,枚举$x\in L,1\leq k<|b|$,将$xb^k$加入$L$中)。每当$L$中有新元素$x$加入,枚举所有$y$使得$y\notin M$且$x$可表示为$y$的幂,把$y$加入$M$中。
  5. 若$L=G$,则找到了所有基,算法结束;否则回到第$3$步

简単でしょう?

复杂度分析

每一轮扩展$L$的复杂度为$O(|L||b|)$,可以看作是$O(n|b|)$,而所有基的阶之和显然为$O(n)$,所以这一步的复杂度为$O(n^2)$。而每个元素只会被加入$L$中至多一次,所以后面那一步的复杂度也为$O(n^2)$。因此算法的总时间复杂度为$O(n^2)$。

查看详细内容

[自选题 #104] [UR #10] 列队

2017-12-21 0:412018-9-13 23:51
集训队作业自选题抽象代数DP容斥群论

传送门

这道题成功让我认识到了我的抽代基本等于没学。。。

题目问的是给定群$G$到$S_n$之间有多少种单同态,其中$S_n$是$n$阶对称群。

先考虑怎么把单同态的限制去掉。根据抽代中的一些理论,$\phi:G_1\to G_2$为单同态当且仅当$\ker \phi=\{e\}$,即$G_1$中只有单位元能映射到$G_2$的单位元。所以,我们只要枚举$G_1$除了$\{e\}$以外的所有正规子群$H$,递归算出满足$\ker \phi=H$的$\phi$有多少种(这等价于求$G_1/H$到$G_2$的单同态数目)。这时如果我们能求出$G_1\to G_2$的同态数目,就能直接容斥得到单同态数目了。

考虑怎么计算$G\to S_n$的同态数目。我们知道,$G\to S_n$的一个同态,对应了群$G$在$\{1,\dots,n\}$上的一个作用。显然,这个作用的轨道之间是独立的,我们可以把每个轨道单独拿出来考虑。

记$\{1,\cdots,n\}$中的某个轨道为$R$,$\phi:G\to S_{|R|}$为同态,则根据抽代中的结论,$|R|$整除$|G|$,且对于任意$r\in R$,$r$的稳定子群$G_r$的陪集和整个轨道$R$一一对应。可以证明(证明过程参见wyy题解),在$1$的稳定子群$G_1$确定的情况下(这里$1$也可以换成别的元素),同态的数目为$(|R|-1)!$,所以总的同态数目为$(|R|-1)!\times($$G$的大小为$\frac{|H|}{|R|}$的子群数$)$。

我们先预处理出$G$的每种大小的子群分别有多少个,然后就能DP啦。设$f_i$表示$G\to S_i$的同态数,我们考虑决策包含$1$的轨道,记$c_k=(k-1)!\times($$G$的大小为$\frac{|H|}k$的子群数$)$,则:$$f_i=\sum_{j=1}^ic_jf_{i-j}\binom{i-1}{j-1}$$

这样我们就完成了对$G\to S_n$的同态数目的统计。找子群可以用广搜,枚举加入的元素,然后跑出包含已有元素的最小子群。最后,容斥的时候有一个小技巧,根据群的第三同构定理,$G$的商群的正规子群一定对应了一个$G$的一个正规子群。所以我们只要在$G$的正规子群里面进行容斥就行了,这样就不用算商群了。总复杂度大概是$O(n_N(n_G+n|G|))$,其中$n_N$为正规子群数,$n_G$为子群数。由于$n_N$和$n_G$都很小,就能直接跑过去啦。

#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#define MAXN 40
#define MAXM 1010
#define LL long long
using namespace std;

const LL P=998244353;

int n,m;
int g[MAXN][MAXN],inv[MAXN],unit;
set<int> s_sg;
vector<int> sg,nsg;
LL c[MAXM][MAXM],fac[MAXM];
LL h[MAXM];

int extend(int s,int x){
    static queue<int> Q;
    s|=1<<(x-1);
    while(1){
        bool flag=0;
        for(int i=1;i<=n;i++)
            if(s&(1<<(i-1)))
                for(int j=1;j<=n;j++)
                    if(s&(1<<(j-1)))
                        if((~s)&(1<<(g[i][j]-1))){
                            flag=1;
                            s|=1<<(g[i][j]-1);
                        }
        if(!flag) return s;
    }
}

bool check_normal(int s){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((s&(1<<(j-1))) && ((~s)&(1<<(g[g[i][j]][inv[i]]-1))))
                return 0;
    return 1;
}

void bfs(){
    static queue<int> Q;
    for(int i=1;i<=n;i++){
        int x=extend(0,i);
        if(!s_sg.count(x)){
            s_sg.insert(x);
            Q.push(x);
        }
    }
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=1;i<=n;i++){
            int y=extend(x,i);
            if(!s_sg.count(y)){
                s_sg.insert(y);
                Q.push(y);
            }
        }
    }
    for(set<int>::iterator it=s_sg.begin();it!=s_sg.end();it++){
        if(check_normal(*it)) nsg.push_back(*it);
        sg.push_back(*it);
    }
}

void dp(int x){
    static int cnt[MAXN];
    memset(cnt,0,sizeof cnt);
    int s=nsg[x],sz=0;
    for(int l=1<<30;l;l>>=1) if(s&l) sz++;
    sz=n/sz;
    for(int i=0;i<sg.size();i++)
        if((sg[i]&s)==s){
            int temp=0;
            for(int l=1<<30;l;l>>=1) if(sg[i]&l) temp++;
            cnt[temp/(n/sz)]++;
        }
    static LL f[MAXM];
    f[0]=1;
    for(int i=1;i<=m;i++){
        f[i]=0;
        for(int j=1;j<=i && j<=sz;j++)
            if(sz%j==0)
                f[i]=(f[i]+c[i-1][j-1]*f[i-j]%P*cnt[sz/j]%P*fac[j-1])%P;
    }
    h[x]=f[m];
    for(int i=x+1;i<nsg.size();i++)
        if((nsg[i]&s)==s) h[x]=(h[x]-h[i])%P;
}

void solve(){
    s_sg.clear();
    sg.clear();
    nsg.clear();
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&g[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(g[i][g[j][k]]!=g[g[i][j]][k]){
                    puts("0");
                    return;
                }
    for(int i=1;i<=n;i++)
        if(g[i][i]==i) unit=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j]==unit)
                inv[i]=j;
    bfs();
    for(int i=nsg.size()-1;i>=0;i--) 
        dp(i);
    printf("%lld\n",(h[0]+P)%P);
}

void init(){
    for(int i=0;i<MAXM;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    }
    fac[0]=1;
    for(int i=1;i<MAXM;i++) fac[i]=fac[i-1]*i%P;
}

int main(){
#ifdef DEBUG
    freopen("104.in","r",stdin);
#endif
    init();
    int T;
    scanf("%d",&T);
    while(T--) solve();
}

查看详细内容