burnside引理与polya定理

$\text{Pólya 定理}$

置换与群

给定一个长度为 $n$ 的环用 $k$ 种颜色染色，有多少种旋转意义下不同的方案

给一个正方形用 $k$ 种颜色染色，有多少种旋转意义下不同的方案

可以统一表达为：给定一个方案集合 $A$ 和 一个变换集合 $S$ ，两个方案等价，如果存在一系列变换使其中一个方案变为另一个

对于这种本质不同的计数问题，通常用置换群来解决

置换的定义

置换使一个双射 $f:\{1,2,..,n\}\rightarrow \{1,2,…,n\}$ 表示将 $i$ 替换为 $f(i)$ ,用记号:

$$\sigma=\begin{pmatrix} 1 & 2 & 3 & ... & n \\ f(1) & f(2) & f(3) & ... & f(n) \\ \end{pmatrix}=(f_1,f_2,f_3,...,f_n)$$

置换也有合成运算，也称为置换的乘法，即：

$$\sigma_1\sigma_2=\begin{pmatrix} i \\ f_1(f_2(i)) \end{pmatrix}$$

置换的性质

循环置换是特殊的置换，具体的，记：

$$\begin{pmatrix} i_1 & i_2 & ... & i_{n-1} & i_n \\ i_2 & i_3 & ... & i_n& i_1 \\ \end{pmatrix} =(i_1,i_2,...,i_n)$$

两个循环置换中若没有相同元素则称它们是不相交的

有定理：任意置换都可以被分解称不相交循环的积

• 证明：

  将元素看作点，映射关系为有向边，每个点的出入度都为 $1$

  那么所得的图一定是若干环的集合，一个环即是一个循环置换

置换乘法的性质

• 结合律显然
• 单位元：有单位置换 $\sigma_1=\binom{i}{i}$
• 可逆性：对任意置换都能找到另一置换使其乘积为单位元
• 消去律：即 $\sigma_1 x=\sigma_1 y\Rightarrow x=y$

对换与置换的奇偶性

对换即是一个 $2$ 轮换，一个循环可以被拆成 $\text{环长-1}$ 个对换

一个 $n$ 轮换可以被拆成 $n-1$ 个对换的积：

$$\begin{pmatrix}1&2&3 \\ 2&3&1\end{pmatrix} =\begin{pmatrix}1&2 \\ 2&1\end{pmatrix} \begin{pmatrix}1&3 \\ 3&1\end{pmatrix}$$

那么对于同一个置换，其有不同的对换分解，但各分解中奇偶性必然相同

定义置换的奇偶性为 $(-1)^{N(\sigma)}$ ，其中 $N(\sigma)$ 为置换能分解成的对换个数

群

一个非空集合 $S$ 和定义在 $S$ 上的二元代数运算 $\circ$ 是群，当且仅当满足：

• 封闭性：二元代数运算得到的结果仍在 $S$ 中
• 结合律
• 单位元，且单位元唯一
• 每个元素均有逆元，且每个元素的逆元唯一

此时再去考虑开头的几个旋转变换：

• 圆环旋转变换构成置换群

  • 运算封闭：旋转 $i^{\circ}$ 与旋转 $j^{\circ}$ 合成，即是旋转 $(i+j)^{\circ}$ 的变换
  • 结合律显然
  • 旋转 $0^{\circ}$ 即是单位元
  • 旋转 $i^{\circ}$ 与旋转 $(360-i)^{\circ}$ 互为逆元

• 正方形旋转变换构成置换群

  • 相当于旋转 $(90k)^{\circ}$，易证

置换群的性质

性质：任何一个存在奇置换的置换群，奇置换与偶置换数量相等

• 证明：
  • 若置换群 $G$ 存在至少一个奇置换 $\sigma_0$ ,用这个奇置换左乘所有的偶置换，得到互异的奇置换，那么奇置换的个数不少于偶置换的个数
  • 相反的，这个奇置换左乘所有的奇置换，得到互异的偶置换，因此奇置换和偶置换数量相等

$\text{Burnside}$ 引理

引入

对 $n$ 个对象 $v_1,v_2,…,v_n$ 按某种原则染上不同颜色，求本质不同方案数

给定置换群 $G$ ，两个方案相同当且仅当存在一个 $\sigma\in G$ 使按 $\sigma$ 对节点做变换染色方案不变

不妨将染色方案看成集合：

$$C=\{c=(c_1,c_2,..,c_n) | c_i表示颜色\}$$

定义置换与染色方案之间的乘法，表示对染色方案进行变换：

$$\sigma \circ c=(c_{\sigma_1},c_{\sigma_2},...,c_{\sigma_n})$$

两个染色方案 $u,v\in C$ 相同，当且仅当存在 $\sigma\in G$ 使：

$$\sigma\circ u=\sigma\circ v$$

稳定核

考虑将染色方案 $c_1$ 变换到 $c_2$ 的置换

若有 $\sigma_1\circ c_1=c_2,\sigma_2\circ c_1=c_2$ 则一定有 $(\sigma_2^{-1}\sigma_1) \circ c_1=c_1$

那么此时，所有能使 $\sigma\circ c=c$ 的置换 $\sigma$ 构成一个子群，检验：

• 运算封闭：若 $\sigma_1,\sigma_2$ 均使 $c$ 不变，则 $\sigma_1\sigma_2$ 也使其不变
• 单位元显然存在
• 逆元：$\sigma_1\circ c=c$ 两边左乘 $\sigma^{-1}$ 即可得 $\sigma^{-1}\circ c=c$

称这个子群 $\text{ker} \ c$ 为 $c$ 的稳定核

陪集分解

对于子群 $c_1$ ,$\sigma_1\approx \sigma_2 \Leftrightarrow \sigma_2^{-1}\sigma_1\in \text{ker} \ c_1$ 是一个等价关系

依靠这个等价关系能将 $C$ 集合划分出若干个等价类，其满足：

• 自反性：单位元在子群中
• 传递性：若 $\sigma_3^{-1}\sigma_2\in \text{ker} \ c,\sigma_2^{-1}\sigma_1\in \text{ker} \ c$ ，由于运算封闭，有 $\sigma_3^{-1}\sigma_1\in \text{ker} \ c$
• 对称性：由于 $\text{ker}\ c$ 是子群， $\sigma_2^{-1}\sigma_1$ 的逆元 $\sigma_1^{-1}\sigma_2$ 也在该子群中

每个划分块为子群 $c_1$ 的一个陪集

陪集分解的性质

考虑 $\text{ker} \ c$ 的每一个陪集 $B$ 的大小

若 $\sigma_1,\sigma_2\in B$ ，则一定有 $x\in \text{ker} \ c$ ,满足 $\sigma_2^{-1}\sigma_1=x\Leftrightarrow \sigma_1=\sigma_2\circ x$

那么用 $\sigma_2$ 右乘 $\text{ker} \ c$ 中的所有元素，得到 $|\text{ker} \ c|$ 个互异的元素

那么这恰好就是 $B$ ，即 $|B|=|\text{ker} \ c|$

那么，将 $c$ 变成 $c_2$ 的置换恰有 $|\text{ker} \ c|$ 种，那么与 $c$ 本质相同的染色方案数恰好为 $\displaystyle{\frac{|G|}{|\text{ker} \ c|}}$

我在写什么？

在写 $\text{burnside}$ 引理之前，看一下刚刚我写了什么

有染色方案 $C$，置换群 $\sigma$ ，其中染色方案 $c_1$ 是 $C$ 的一个子集，$\text{ker} \ c_1$ 是置换群 $\sigma$ 的一个子群，也是 $c_1$ 的稳定核，陪集 $B$ 是 $\text{ker} \ c$ 的一个子群

$\text{burnside}$ 引理

每种颜色对于等价类个数的贡献，是其所在等价类的倒数，那么等价类的个数就是

$$\sum_{c\in C}\frac{|\text{ker} \ c|}{|G|}=\frac{1}{|G|} \sum_{c\in C} |\text{ker} \ c|$$

那么，枚举染色方案对不动置换求和，恰是枚举置换方案并对染色方案求和

设 $G$ 为置换群，$X(\sigma)$ 是在置换 $\sigma$ 下不变的染色方案数，那么本质不同的染色方案为

$$|X/G|=\frac{1}{|G|}\sum_{\sigma\in G}|X(\sigma)|$$

$\text{Pólya}$ 定理

考虑更快的使用 $\text{burnside}$

对于求本质不同的问题中(即使用 $\text{burnside}$ 时)，要求不动点的数量

定义 $c(\sigma)$ 表示置换 $\sigma$ 的轮换数，那么有：

$$|X/G|=\frac{1}{|G|}\sum_{\sigma\in G} m^{c(\sigma)}$$

$m$ 为可用颜色数

例题

一个例子

两种颜色给 $2\times 2$ 正方形染色，本质不同的着色数

考虑每个置换：

• 旋转 $0^{\circ}$ ：不动的染色方案为 $2^4$ 种：显然任意染色即可
• 旋转 $90^{\circ}$ ：不动的染色方案为 $2$ 种：只有全染和全不染
• 旋转 $180^{\circ}$ ：不动的染色方案为 $2^2$ 种：全染全不染+染对角线
• 旋转 $270^{\circ}$ ：不动的染色方案为 $2$ 种：只有全染全不染

那么共 $\frac{16+2+4+2}{4}=6$ 种

P4980 【模板】Pólya 定理

长度为 $n$ 的圆环用 $m$ 种颜色染色，求旋转意义下本质不同方案数

旋转对环的影响就相当于对 $n$ 个珠子进行一次 $\{f_1,f_2,…,f_n\}$ 的置换，所有的旋转方案构成大小为 $n$ 的置换群

根据 $\text{burnside}$ 引理，需要枚举每个置换，找其不动点的个数

• 在置换情况下找染色后不动的点

  此题中，将每种置换看成旋转 $x$ 个位置，该置换下不动的染色方案数，相当于对于每个 $i$ 都有 $c_i=(c_i+x-1)\ \text{mod}\ n+1$ ，$c_i$ 表示不旋转情况下第 $i$ 个珠子的染色情况

• 相同轮换内染同种颜色

  将强制相同的珠子并为一个集合，相当于每个集合强制染同一种颜色，即，将这个置换分解为多个轮换，属于同一个轮换的染成同种颜色

• 一个轮换看成一个集合，所有集合组成新环，在新环上进行不考虑同构的染色

  由线性同余方程可得，如此划分共有 $\gcd(x,n)$ 中集合，每个集合有 $\frac{n}{\gcd(x,n)}$ ，其中第 $i$ 个珠子属于第 $(i-1)\ \text{mod}\ \gcd(x,n)+1$ 个集合

  那么此时，在第 $i$ 个集合中的珠子在原圆环上相邻的两个点分别属于第 $i-1,i+1$ 个集合，特别的，集合 $1$ 与 $\gcd(n,x)$ 也看做是相邻的

  那么对相邻珠子染色的限制可以转移为对相邻集合的染色限制，那么不妨将这 $\gcd(n,x)$ 个集合看成一个长度 $\gcd(n,x)$ 的新环

那么答案就是：

$$\frac{1}{n}\sum_{x=1}^{x=n} k^{\gcd(n,x)}$$

枚举的 $d$ 不考虑循环同构，其实是枚举集合构成的环的大小

化简后有：

$$\begin{aligned} 原式&=\frac{1}{n}\sum_{d\mid n} m^d\sum_{d\mid x} \left[\gcd\left(\frac{n}{d},\frac{x}{d}\right)=1 \right] \\ &=\frac{1}{n}\sum_{d\mid n}m^d\sum_{k\leq \frac{n}{d}} \left[\gcd\left(\frac{n}{d},k\right)=1 \right] \\ &=\frac{1}{n}\sum_{d\mid n}m^d\varphi\left(\frac{n}{d} \right) \end{aligned}$$

const int mod=1e9+7;
int t,n,ans;

inline void fix(int &x){ x>=mod ? x-=mod : 0;}
inline int qpow(ll x,int y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;} return res;}

inline int get_phi(int x){
    rei res=x,tmp=x;
    for(rei i=2;i*i<=tmp;++i){
        if(!(x%i)){
            res=(ll) res*(i-1)/i%mod;
            while(!(x%i)) x/=i;
        }
    }
    if(x>1) res=(ll) res*(x-1)/x%mod;
    return res;
}

int main(){
    rei T; scanf("%d",&T);
    while(T--){
        scanf("%d",&n); ans=0;
        for(rei i=1;i*i<=n;++i){
            if(n%i) continue;
            fix(ans+=(ll) qpow(n,i)*get_phi(n/i)%mod);
            if(i*i!=n) fix(ans+=(ll) qpow(n,n/i)*get_phi(i)%mod);
        }
        printf("%d\n",(ll) ans*qpow(n,mod-2)%mod);
    }
    getchar(),getchar();
    return 0;
}

P4916 [MtOI2018]魔力环

$m$ 个黑珠子和 $n-m$ 个白珠子串成环，满足环上不会出现一段长度超过 $k$ 的连续黑珠子，求旋转环不相同的方案数

设 $f(n,m)$ 表示 $m$ 个黑珠子和 $n-m$ 个白珠子串成一个环的方案数

那么套路的得答案为：

$$\frac{1}{n}\sum_{d\mid n}\left[m\mid \frac{n}{d} \right] f\left(d,\frac{m}{\frac{n}{d}}\right)\varphi\left(\frac{n}{d} \right)$$

显然 $\displaystyle{\frac{m}{\frac{n}{d}}}$ 是 $m$ 在环中存在的个数 这个很难描述

考虑求 $f(n,m)$ ：断环为链

特殊的：当 $m\leq k$ 时 $f(n,m)=\binom{n}{m}$ ，即黑珠子任意放

处理环的特殊情况：枚举第一个白珠左边的黑珠数量与最后一个白珠右边的黑珠数量之和 $i$ ，显然有 $0\leq i\leq k$ ，对每个 $i$ ，有 $i+1$ 中摆放黑珠的方法

剩下的部分就可以被看作链上问题：即，将 $m-i$ 个黑珠插进 $n-m$ 个白珠的间隙； 转化为将 $m-i$ 个黑珠分成 $n-m-1$ 段，且每段的长度 $\leq k$ 的方案数

设 $g(n,m)$ 表示 $n$ 个珠子分成 $m$ 段，每段 $\leq k$ 的方案数，通过容斥，枚举有 $i$ 段的长度超过 $k$ ，得：

$$g(n,m)=\sum_{i=0}^{\min\left(m,\left\lfloor\frac{n}{k+1} \right\rfloor\right)} (-1)^i \binom{m}{i}\binom{n-i*(k+1)+m-1}{m-1}$$

那么就能有：

$$f(n,m)= \begin{cases} \binom{n}{m} &\text{ $m\leq k$ } \\ \sum_{i=0}^k g(m-i,n-m-1) &\text{ $m>k$ } \\ \end{cases}$$

$f$ 带回原式即可

const int N=2e5+100;
const int mod=998244353;
int n,m,k,ans;
int phi[N],fac[N],inv[N],facinv[N];
int sie[N],prime[N],cnt;

inline void fix(int &x){ x>=mod ? x-=mod : 0; x<0 ? x+=mod : 0;}
inline int get_C(int n,int m){ if(n<m || n<0 || m<0) return 0; return (ll) fac[n]*facinv[m]%mod *facinv[n-m]%mod;}
inline void init(){
    fac[0]=facinv[0]=inv[1]=1;
    for(rei i=1;i<=n;++i){
        if(i>1) inv[i]=(ll) inv[mod%i]*(mod-mod/i)%mod;
        fac[i]=(ll) fac[i-1]*i%mod;
        facinv[i]=(ll) facinv[i-1]*inv[i]%mod;
    }
    phi[1]=1;
    for(rei i=2;i<=n;++i){
        if(!sie[i]) prime[++cnt]=i,phi[i]=i-1;
        for(rei j=1;j<=cnt && (ll) prime[j]*i<=n;++j){
            rei x=prime[j]*i;
            sie[x]=1;
            if(!(i%prime[j])){ phi[x]=phi[i]*prime[j]; break;}
            else phi[x]=phi[i]*(prime[j]-1);
        }
    }
}

inline int get_g(int n,int m){
    rei res=0,lim=min(m,n/(k+1));
    for(rei i=0;i<=lim;++i){
        rei tmp=(ll) get_C(m,i)*get_C(n-i*(k+1)+m-1,m-1)%mod;
        fix(res+=(ll) tmp*(i&1 ? mod-1 : 1)%mod);
    }
    return res;
}

inline int get_f(int n,int m){
    if(m<=k) return get_C(n,m);
    else if(n==m+1) return 0;
    rei res=0;
    for(rei i=0,tmp=n-m-1;i<=k;++i) fix(res+=(ll) (i+1)*get_g(m-i,tmp)%mod);
    return res;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    if(n==m) return puts(k>=n ? "1" : "0"),0;
    init();
    for(rei d=1;d<=n;++d) if(!(n%d) && !(m%(n/d)))
        fix(ans+=(ll) get_f(d,m/(n/d))*phi[n/d]%mod);
    printf("%d\n",(ll) ans*inv[n]%mod);
    getchar(),getchar();
    return 0;
}

P3307 [SDOI2013]项链

$n$ 个珠子串成一个环，每个珠子是一个正三棱柱，三个侧面刻有数字，每个数字 $x$ 满足 $1\leq x\leq a$ ，珠子上三个数字 $\gcd=1$ 。两个珠子相同当且仅当三棱柱通过旋转或翻转能使对应面数字相同，相邻两个珠子必须不同，

若两个项链能通过旋转变成一样的则认为两个项链相同，求不同的项链个数

题中出现了两个本质不同：本质不同的珠子与 $\gcd$ 有关，用莫反解；本质不同的项链与旋转有关，用 $\text{burnside}$

• 先考虑珠子

  由 $\text{burnside}$ 引理：珠子的置换群共有 $6$ 个，每个置换下的不动点数就是将置换分解为 $k$ 个轮换后，最大公约数为 $1$ 的有序 $k$ 元组数量

  置换群的方案即是：旋转 $0/1/2$ 格，按照第 $0/1/2$ 格翻转，每个置换的轮换数分别为 $3,1,1,2,2,2$

  设 $S_i$ 表示有序 $i$ 元组的数量，那么珠子的个数即为

  $$\frac{2\times S_1+3\times S_2+S_3}{6}$$

  显然 $S_1$ 只有一个 $(1,1,1)$

  $S_2$ 是满足互质的二元组个数，即 $\sum_{i=1}^a\sum_{j=1}^a [\gcd(i,j)=1]$

  通过莫反显然能得到：

  $$F(n)=\sum_{i=1}^a\sum_{j=1}^a[\gcd(i,j)=n]$$ $$G(n)=\sum_{n\mid d}F(d)=\sum_{i=1}^a\sum_{j=1}^a[n\mid \gcd(i,j)]=\left[\frac{a}{n}\right]^2$$ $$F(n)=\sum_{n\mid d}G(d)\times \mu\left(\frac{d}{n} \right)$$

  那么所求即是 $F(1)=\sum_{i=1}^a G(i)\mu(i)=\sum_{i=1}^a \left[\frac{a}{i} \right]^2\mu(i)$

  $S_3$ 同理可得 $\sum_{i=1}^a\left[\frac{a}{i} \right]^3 \mu(i)$

• 再考虑不同项链数

  套路的，用 $\text{burnside}$ 得

  $$\frac{1}{n}\sum_{d\mid n}f(d)\varphi\left(\frac{n}{d} \right)$$

  $f$ 为大小为 $d$ 个集合的环不考虑同构情况下的方案数

  考虑 $f_n$ 的递推：插入第 $n$ 个珠子时，若 $1$ 与 $n-1$ 个珠子相同，则方案数为 $(m-1)f_{n-2}$ ，若不同，方案数为 $(m-2)f_{n-1}$

  那么有 $f_n=(m-1)f_{n-2}+(m-2)f_{n-1}$ ，为方便计算，不妨设 $f_0=m,f_1=0$ ，那么就可以矩乘优化

  但注意到这个形式恰是二阶常系数线性齐次递推式

  具体的，可以列出 $\lambda^2-(m-2)\lambda-(m-1)=0$ 来求得两个特征根 $\lambda_1=-1,\lambda_2=m-1$

  设 $c=f_1-\lambda_1f_0=m$

  由于此时 $\lambda_1\not ={\lambda_2}$ ，由等比数列求和能解得：

  $$A=f_0-\frac{c}{\lambda_2-\lambda_1}=m-1$$ $$B=\frac{c}{\lambda_2-\lambda_1}=1$$

  那么有：

  $$f_n=Ax_1^n+Bx_2^n=(m-1)(-1)^n+(m-1)^n$$

const int N=1e7+100;
const ld EPS=0.5;
const ll mod=1e9+7;
const ll mod_2=mod*mod;
const ll inv6=833333345000000041ll;

bool vis[N];
int prime[N/10],pri_cnt,mu[N];
ll n,m,ans,limit;
int a,cnt;
ll q_n[11],q_a[11];
ll varphi[N/10],num[N/10];

inline void fix(ll &x){ x>=mod_2 ? x-=mod_2 : 0;}
inline ll qmul(ll x,ll y){ return (x*y-(ll) (((ld) x*y+EPS)/(ld) mod_2)*mod_2+mod_2)%mod_2;}
inline ll lpow(ll x,ll y,ll res=1){ while(y){ if(y&1) res=qmul(res,x); y>>=1; x=qmul(x,x);} return res;}
inline ll qpow(ll x,ll y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;} return res;}
inline ll sqr(ll x){ return qmul(x,x);}
inline ll cub(ll x){ return qmul(sqr(x),x);}

inline void init(ll lim){
    mu[1]=1;
    for(rei i=2;i<=lim;++i){
        if(!vis[i]) prime[++pri_cnt]=i,mu[i]=-1;
        for(rei j=1;j<=pri_cnt && i*prime[j]<=lim;++j){
            rei x=i*prime[j]; vis[x]=1;
            if(i%prime[j]) mu[x]=-mu[i];
            else break;
        }
    }
    for(rei i=1;i<=lim;++i) mu[i]+=mu[i-1];
}

inline ll calc_pearl(ll n){
    ll S2=0,S3=0,S1=1,res=0; S1*=2;
    for(rei i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        fix(S3+=qmul(cub(n/i),(mu[j]-mu[i-1]+mod_2)%mod_2));
        fix(S2+=qmul(sqr(n/i),(mu[j]-mu[i-1]+mod_2)%mod_2));
    }
    fix(res+=S3); fix(res+=qmul(S2,3)); fix(res+=S1);
    return qmul(res,inv6);
}

inline ll get_f(ll n){
    ll res=lpow(m-1,n);
    fix(res+=n&1 ? (mod_2-(m-1))%mod_2 : m-1);
    return res;
}

void get_phi(int depth,ll d,ll phi){
    if(depth==cnt+1) return fix(ans+=qmul(phi,get_f(n/d)));
    get_phi(depth+1,d,phi);
    d*=varphi[depth]; phi*=varphi[depth]-1;
    get_phi(depth+1,d,phi);
    for(rei i=2;i<=num[depth];++i) d*=varphi[depth],phi*=varphi[depth],get_phi(depth+1,d,phi);
}

int main(){
    rei T; scanf("%d",&T);
    for(rei i=1;i<=T;++i) scanf("%lld%lld",&q_n[i],&q_a[i]),limit=max(limit,max( (ll) sqrt(q_n[i]),q_a[i]));
    init(limit);
    for(rei ith=1;ith<=T;++ith){
        n=q_n[ith],a=q_a[ith];
        m=calc_pearl(a);
        cnt=ans=0; ll x=n;
        for(rei i=1;i<=pri_cnt && (ll) prime[i]*prime[i]<=x;++i){
            if(x%prime[i]) continue;
            varphi[++cnt]=prime[i]; num[cnt]=0;
            while(!(x%prime[i])) ++num[cnt],x/=prime[i];
        }
        if(x>1) varphi[++cnt]=x,num[cnt]=1;
        get_phi(1,1,1);
        if(!(n%mod)) ans=(ll) (ans/mod)*qpow(n/mod,mod-2)%mod;
        else ans=(ll) (ans%mod)*qpow(n%mod,mod-2)%mod;
        printf("%lld\n",ans);
    }
    getchar(),getchar();
    return 0;
}

P5564 [Celeste-B]Say Goodbye

$m$ 种颜色的 $n$ 个珠子，每种颜色有 $a_i$ 个，将 $n$ 个珠子串成环长 $\geq 2$ 的无向基环树，基环树的两个子树不同当且仅当其对应点颜色不同或两子树不同构。两树同构当且仅当两个根每个儿子的子树对应同构，且儿子有顺序

如果两基环树可以旋转基环而相同，则认为本质相同，求多少多少本质不同的基环树

先考虑 $n$ 个点的无标号有根有序树的方案，考虑长度为 $n$ 的括号序列，但考虑到最外层括号(根节点)只能有一对括号，那么方案数即为 $\text{Cat}_{n-1}$

再考虑基环树的方案，设 $C(x)$ 是 $\text{Cat}$ 的生成函数，$T(x)$ 是基环树方案的生成函数，那么有 $T(x)=xC(x)$ ，即多加一条边

那么环长 $k$ 的基环树相当于 $k$ 棵大小和为 $n$ 的无标号有根有序树，考虑 $\text{burnside}$ 引理，枚举环长 $k$ 得：

$$ans=\sum_{k=2}^n \frac{1}{k}\sum_{d\mid k} f_k\left(\frac{k}{d} \right)\varphi(d)$$

$f_k(d)$ 表示环长 $k$ 的基环树，限制环上 $\text{mod}\ d$ 相同的位置的子树完全一样的方案数(此时不考虑旋转同构)

$f_k\left(\frac{k}{d} \right)$ 即要求 $\text{mod}\ \frac{k}{d}$ 相同的位置完全一样，即每个等价类的元素个数为 $d$ 个

那就是将所有的 $n$ 个点分成 $d$ 份，每一份拼成 $\frac{k}{d}$ 棵大小之和为 $\frac{n}{d}$ 的无标号有根有序树

考虑到每一棵树大小都不能为 $0$ ，那么生成函数常数项为 $0$ ，$k$ 棵大小之和为 $n$ 的树的方案数即为 $\left[x\right]^n (xC)^k$

考虑到染色与树形态相独立，还需要乘一个多重组合数 $\displaystyle{\binom{n}{a_1,a_2,…,a_m}}$

设

$$g(d)=\binom{\frac{n}{d}}{\frac{a_1}{d},\frac{a_2}{d},...,\frac{a_m}{d}}$$

那么有

$$\begin{aligned} ans&=\sum_{k=2}^n\frac{1}{k}\sum_{d\mid k} \left[d\mid \gcd_{i=1}^n a_i \right] \varphi(d)\times g(d)\times \left[x^{\frac{n}{d}} \right] (xC)^{\frac{k}{d}}\\ &\text{后面的式子表示的即是生成函数 $C(x)$ 的第 $\frac{n}{d}$ 项的系数} \\ &=-\text{Cat}_{n-1}g(1)+\sum_{d\mid \gcd}\varphi(d)g(d)\sum_{d\mid k}\left[x^{\frac{n}{d}} \right]\frac{(xC)^{\frac{k}{d}}}{k} \\ &=-\text{Cat}_{n-1}g(1)+\sum_{d\mid \gcd}\varphi(d)g(d)\times \frac{1}{d}\times \sum_{k=1}^{\frac{n}{d}} \left[x^{\frac{n}{d}-k} \right]\frac{C^k}{k} &\text{套路的枚举 $k$ 倍的 $d$ ，所以要乘上 $\frac{1}{d}$}\\ \end{aligned}$$

考虑一个很神仙的式子：

$\displaystyle{[x^n]C^m}$ 是卡塔兰数与自身卷积 $m$ 次后第 $n$ 项的通项，有：

$$[x^n]C^m=\binom{2n+m-1}{n}-\binom{2n+m-1}{n-1}$$

那么带入直接计算即可

const int N=4e5+100;
const int mod=998244353;
int phi[N];
int fac[N],facinv[N],inv[N];
int n,m,cnt[N],ans;

inline void fix(int &x){ x>=mod ? x-=mod : 0;x<0 ? x+=mod : 0;}
inline int get_C(int n,int m){ if(n<0 || m<0 || n<m) return 0; return (ll) fac[n]*facinv[m]%mod*facinv[n-m]%mod;}
inline int catalan_powm(int n,int m){ return (get_C(n*2+m-1,n)-get_C(n*2+m-1,n-1)+mod)%mod;}
inline void init(int lim){
    for(rei i=1;i<=lim;++i){
        phi[i]+=i;
        for(rei j=i<<1;j<=lim;j+=i) fix(phi[j]-=phi[i]);
    }
    fac[0]=facinv[0]=1;
    for(rei i=1;i<=lim;++i){
        fac[i]=(ll) fac[i-1]*i%mod;
        inv[i]=i==1 ? 1 :(ll) inv[mod%i]*(mod-mod/i)%mod;
        facinv[i]=(ll) facinv[i-1]*inv[i]%mod;
    }
}

inline int get_g(int d){
    int res=fac[n/d];
    for(rei i=1;i<=m;++i) res=(ll) res*facinv[ cnt[i]/d ]%mod;
    return res;
}

int main(){
    scanf("%d%d",&n,&m); rei lim_d=n;
    for(rei i=1;i<=m;++i) scanf("%d",&cnt[i]),lim_d=__gcd(lim_d,cnt[i]);
    init(N-1);
    for(rei d=1;d<=lim_d;++d)
        if(!(lim_d%d)){
            rei prod=(ll) phi[d]*inv[d]%mod*get_g(d)%mod;
            rei sum=0;
            for(rei k=1,lim=n/d;k<=lim;++k) fix(sum+=(ll) inv[k]*catalan_powm(lim-k,k)%mod);
            fix(ans+=(ll) prod*sum%mod);
        }
    fix(ans-=(ll) catalan_powm(n-1,1)*get_g(1)%mod);
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}