传送门

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

题目问的是给定群$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();
}