[自选题 #104] [UR #10] 列队
这道题成功让我认识到了我的抽代基本等于没学。。。
题目问的是给定群$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();
}