做招聘网站代理商需要多少钱,wordpress菜单栏不显示不出来,免费pc网站建设,谷歌站群系统群与子群 G,opG,opG,op 是一个群需要满足以下条件#xff1a; opopop 是一个满足结合律的二元运算#xff0c;如 *#xff0c;。GGG 是一个集合#xff0c;存在单位元 eee。GGG 中所有元素都有逆元。即 GGG 对 opopop 运算封闭#xff0c;封闭简单…群与子群
G,opG,opG,op 是一个群需要满足以下条件
opopop 是一个满足结合律的二元运算如 *。GGG 是一个集合存在单位元 eee。GGG 中所有元素都有逆元。即 GGG 对 opopop 运算封闭封闭简单理解就是元素的逆元也在里面有单位元任意两个数二元运算结果也在里面。
这里的单位元逆元结合律按照一般的意思来理解即可。
虽然没有要求满足交换律但还是定义逆元是 xx−1x−1xexx^{-1}x^{-1}xexx−1x−1xe。
如果还满足交换律就叫做交换群。
群内元素只有“乘法”这一种运算规则这个“乘法”指的就是 opopop 运算。
例如op那么 xyxy,xx−1xx−1exyxy,xx^{-1}xx^{-1}exyxy,xx−1xx−1e。
H,opH,opH,op 是 G,opG,opG,op 的子群满足两个条件
HHH 是 GGG 的子集。H,opH,opH,op 是个群。
阶
群元素个数有穷时阶就等于元素个数。
置换群
映射两个集合之间元素的对应关系可能一对多多对一一对一等。
置换有限集合到自身的双射即一一对应。
设 S{a1,a2,...,an}S\{a_1,a_2,...,a_n\}S{a1,a2,...,an} 的一个置换 f(a1a2…anap1ap2…apn)f\begin{pmatrix}a_1\quad a_2\quad\dots\quad a_n\\a_{p_1}\quad a_{p_2}\quad\dots\quad a_{p_n}\end{pmatrix}f(a1a2…anap1ap2…apn)。
表示将 aia_iai 映射成 apia_{p_i}api即 aiapia_ia_{p_i}aiapi。其中 p1,...,pnp_1,...,p_np1,...,pn 是一个 nnn 元排列。
显然 SSS 上所有的置换个数为 n!n!n!。
置换的乘法即函数的合成。
对于两个置换 f(a1a2…anap1ap2…apn),g(ap1ap2…apnaq1aq2…aqn)f\begin{pmatrix}a_1\quad a_2\quad\dots\quad a_n\\a_{p_1}\quad a_{p_2}\quad\dots\quad a_{p_n}\end{pmatrix},g\begin{pmatrix}a_{p_1}\quad a_{p_2}\quad\dots\quad a_{p_n}\\a_{q_1}\quad a_{q_2}\quad\dots\quad a_{q_n}\\\end{pmatrix}f(a1a2…anap1ap2…apn),g(ap1ap2…apnaq1aq2…aqn)fff 和 ggg 的乘积记为 f∘g(a1a2…anaq1aq2…aqn)f\circ g\begin{pmatrix}a_1\quad a_2\quad\dots\quad a_n\\a_{q_1}\quad a_{q_2}\quad\dots\quad a_{q_n}\\\end{pmatrix}f∘g(a1a2…anaq1aq2…aqn)。
即先做 fff 的映射再做 ggg 的映射。
定义 Sn{S_n\{Sn{ 所有的 nnn 元排列 }\}}。装备了乘法opopop的 SnS_nSn 的子群叫做 nnn 元置换群。
循环置换
循环置换是一类特殊的置换表示为 (a1,a2,...,am)(a1,a2,...,am−1,ama2,a3,...,am,a1)(a_1,a_2,...,a_m)\begin{pmatrix}a_1,a_2,...,a_{m-1},a_m\\a_2,a_3,...,a_m,a_1\end{pmatrix}(a1,a2,...,am)(a1,a2,...,am−1,ama2,a3,...,am,a1)。
若两个置换不含有相同的元素则称它们是不相交的。
举个例子 A(a1,a2a2,a1),B(a4,a5,a6a5,a4,a6)A\begin{pmatrix}a_1,a_2\\a_2,a_1\end{pmatrix},B\begin{pmatrix}a_4,a_5,a_6\\a_5,a_4,a_6\end{pmatrix}A(a1,a2a2,a1),B(a4,a5,a6a5,a4,a6)则 A,BA,BA,B 就是不相交的所含元素集合的交为空。
任何一个置换都可以分解成若干个≥1\ge 1≥1不相交的循环置换的乘积。
举个例子(a1,a2,a3,a4,a5,a6a2,a1,a3,a6,a4,a5)(a1,a2)∘(a3)∘(a5,a6,a4)\begin{pmatrix}a_1,a_2,a_3,a_4,a_5,a_6\\a_2,a_1,a_3,a_6,a_4,a_5\end{pmatrix}(a_1,a_2)\circ(a_3)\circ(a_5,a_6,a_4)(a1,a2,a3,a4,a5,a6a2,a1,a3,a6,a4,a5)(a1,a2)∘(a3)∘(a5,a6,a4)。 证明很简单将元素看作点映射关系当成边则每个节点的入度和出度都为 111。形成的图形必然是若干个环集合而一个环就代表一个循环置换。 群的陪集分解
设 GGG 是群HHH 是 GGG 的子群a∈Ga\in Ga∈G。
定义 Ha{h∣ha∈H}Ha\{h\mid ha\in H\}Ha{h∣ha∈H}。这里的 hahaha 做乘法是群的运算符号即 h(op)ah(op)ah(op)a。
称 HaHaHa 是子群 HHH 的在 GGG 中的一个右陪集。
显然 HeH,a∈HaH_eH,a\in HaHeH,a∈Ha。 ∀a∈G\forall a\in G∀a∈G 有 H,HaH,HaH,Ha 等势。集合大小相同 证明构造从 H→HaH\rightarrow HaH→Ha 的双射只需让 f(h)haf(h)haf(h)ha 即可。 这说明在有限集的情况HHH 与 HaHaHa 的阶相同。
∀a,b∈G,a∈Hb\forall a,b\in G,a\in Hb∀a,b∈G,a∈Hb 等价于 ab−1∈Hab^{-1}\in Hab−1∈H 等价于 HaHbHaHbHaHb 。 证明a∈Hb⇒ab−1∈H⇒Hab−1∈Ha\in Hb\Rightarrow ab^{-1}\in H\Rightarrow Hab^{-1}\in Ha∈Hb⇒ab−1∈H⇒Hab−1∈HHHH 是群对内部元素是封闭的⇒Ha∈Hb\Rightarrow Ha\in Hb⇒Ha∈Hb。 基于此我们可以定义等价类关系并进行等价类分解。
定义等价类关系∀a,b∈G,ab−1∈H\forall a,b\in G,ab^{-1}\in H∀a,b∈G,ab−1∈H则将 a,ba,ba,b 划分在同一个等价类里面。以 HHH 为判定条件划分 GGG 这个群空间
同时得到 lagrange定理。 拉格朗日定理设 GGG 是有限群HHH 是 GGG 的子群则 GGG 的阶一定是 HHH 阶的倍数具体是多少倍看能分出多少个等价类来。 将 GGG 划分成 Ha,Hb,...,HHa,Hb,...,HHa,Hb,...,H任意两个 ab−1∉Hab^{-1}\not\in Hab−1∈H而上面又证明了 ∣Ha∣∣H∣∣Hb∣...|Ha||H||Hb|...∣Ha∣∣H∣∣Hb∣... 每个等价类的大小是一样的。 左陪集 aHaHaH 与右陪集完全一样不再赘述。
轨道-稳定子集定理
设 GGG 是集合 Ω\OmegaΩ 上的有穷置换群。a∈Ωa\in \Omegaa∈Ω。
定义 Ga{g∣g∈G∧g(a)a}G^a\{g\mid g\in G\wedge g(a)a\}Ga{g∣g∈G∧g(a)a}称 GaG^aGa 为 aaa 的稳定子群。
解释aaa 是一个数ggg 是一个置换GaG^aGa 是所有置换 ggg 满足 ggg 作用于 aaa 后仍是 aaa 不变的集合。
举个例子一个置换 g(1234553241)g\begin{pmatrix}1\ 2\ 3\ 4\ 5\\5\ 3\ 2\ 4\ 1\end{pmatrix}g(1 2 3 4 55 3 2 4 1)那么 G4G^4G4 就会含有这个 ggg。
定义 G(a){g(a)∣g∈G}G(a)\{g(a)\mid g\in G\}G(a){g(a)∣g∈G}称 G(a)G(a)G(a) 为 aaa 的轨道。
解释aaa 是一个数ggg 是一个置换g(a)g(a)g(a) 是 ggg 作用于 aaa 后的值G(a)G(a)G(a) 是这些值的集合。
即 GGG 中所有置换作用于 aaa 后可能的值的集合。
举个例子一个置换 g∈G,g(1234553241)g\in G,g\begin{pmatrix}1\ 2\ 3\ 4\ 5\\5\ 3\ 2\ 4\ 1\end{pmatrix}g∈G,g(1 2 3 4 55 3 2 4 1)那么 G(1)G(1)G(1) 就会含有 555G(2)G(2)G(2) 就会含有 333。
轨道-稳定子集定理∣G∣∣G(a)∣∣Ga∣\big|G\big|\big|G(a)\big|\big|G^a\big|∣∣G∣∣∣∣G(a)∣∣∣∣Ga∣∣。 证明 首先显然 GaG^aGa 是 GGG 的子群GaG^aGa 对置换作用在置换上的这个二元运算封闭。 考虑陪集分解任取两个置换 x,y∈G,x(a)y(a)⇔x−1(x(a))ax−1(y(a))⇔x−1y∈Ga⇔xGayGax,y\in G,x(a)y(a)\Leftrightarrow x^{-1}(x(a))ax^{-1}(y(a))\Leftrightarrow x^{-1}y\in G^a\Leftrightarrow xG^ayG^ax,y∈G,x(a)y(a)⇔x−1(x(a))ax−1(y(a))⇔x−1y∈Ga⇔xGayGa。 这说明 xxx 和 yyy 在 GGG 关于 GaG^aGa 的陪集分解的同一个等价类中当且仅当 x(a)y(a)x(a)y(a)x(a)y(a)。 也就是说 ∣G(a)∣|G(a)|∣G(a)∣是 GGG 关于 GaG^aGa 的陪集分解的等价类的个数。 由拉格朗日定理知等价类的个数也就是 GGG 的阶是 GaG^aGa 的阶的倍数。 得证。 burnside 引理
设 A,BA,BA,B 为有限集合。
GGG AAA 上的置换群ggg ∈G\in G∈G 的一个置换。
X:X:X: 一些从 AAA 到 BBB 的映射集合且 XXX 在 GGG 下封闭。
X/G:GX/G:GX/G:G 作用在 XXX 上产生的所有等价类集合。
若 XXX 的两个映射经过 GGG 的置换作用后相同则在同一个等价类中
C(g)C(g)C(g) ggg 作用在元素后不变的元素集合大小即 C(g)∣Xg∣,Xg{a∣g(a)a}C(g)|X^g|,X^g\{a\mid g(a)a\}C(g)∣Xg∣,Xg{a∣g(a)a}。 ∣X/G∣1∣G∣∑g∈GC(g)∑a∈A1∣G(a)∣|X/G|\frac{1}{|G|}\sum_{g\in G}C(g)\sum_{a\in A}\frac 1{|G(a)|} ∣X/G∣∣G∣1g∈G∑C(g)a∈A∑∣G(a)∣1 证明 ∑g∈GC(g)∑a∈A∣Ga∣∑a∈A∣G∣∣G(a)∣∣G∣∑a∈A1∣G(a)∣⇒1∣G∣∑g∈GC(g)∑a∈A1∣G(a)∣∣X/G∣\sum_{g\in G}C(g)\sum_{a\in A} |G^a|\sum_{a\in A}\frac{|G|}{|G(a)|}|G|\sum_{a\in A}\frac{1}{|G(a)|}\Rightarrow \frac{1}{|G|}\sum_{g\in G}C(g)\sum_{a\in A}\frac{1}{|G(a)|}|X/G| g∈G∑C(g)a∈A∑∣Ga∣a∈A∑∣G(a)∣∣G∣∣G∣a∈A∑∣G(a)∣1⇒∣G∣1g∈G∑C(g)a∈A∑∣G(a)∣1∣X/G∣ ∑g∈GC(g):\sum_{g\in G}C(g):∑g∈GC(g): 枚举置换然后累和每个置换中不动点的个数。 ∑a∣Ga∣:\sum_a|G^a|:∑a∣Ga∣: 枚举数然后累和满足 aaa 为不动点的置换个数。 二者只是枚举出发方向不同但结果是相同的。 ∑a1∣G(a)∣:\sum_a\frac 1{|G(a)|}:∑a∣G(a)∣1: 由轨道-稳定子集定理我们知道以 aaa 为分解参照 G(a)G(a)G(a) 内的所有元素构成一个等价类。 由陪集分解知GGG 是一个群无论 aaa 是什么所有等价类都是大小一样的。 那么假设 ∣G(a)∣x|G(a)|x∣G(a)∣x即所有等价类的大小均为 xxx每个数都会贡献 1x\frac{1}{x}x1∣G∣∗1x|G|*\frac{1}{x}∣G∣∗x1 得到的就是等价类的个数即 ∣X/G∣|X/G|∣X/G∣。 polya 定理
定义加强 X:X:X: 所有 AAA 到 BBB 的映射定义 c(g):c(g):c(g): 置换 ggg 能拆分成的不相交的循环置换的个数。即环的个数。 ∣X/G∣1∣G∣∑g∈G∣B∣c(g)|X/G|\frac{1}{|G|}\sum_{g\in G}|B|^{c(g)} ∣X/G∣∣G∣1g∈G∑∣B∣c(g) 例如对于有 nnn 个点形成的环 mmm 种颜色的染色问题A{1,2,...,n},B{1,2,...,m}A\{1,2,...,n\},B\{1,2,...,m\}A{1,2,...,n},B{1,2,...,m}∣Xg∣mc(g)|X^g|m^{c(g)}∣Xg∣mc(g)。
将置换看作图上的一条有向边若置换后 u→vu\rightarrow vu→v就连一条有向边。那么就形成若干个环环中元素的颜色一定相同。 在 OIOIOI 中一般求本质不同的方案数本质不同就是不再同一个等价类换言之一般考察的问题答案就是等价类个数 ∣X/G∣|X/G|∣X/G∣。
经典例题poj2154
∣X/G∣1∣G∣∑g∈Gmc(g)⇒ans1n∑i1nn(n,i)|X/G|\frac{1}{|G|}\sum_{g\in G}m^{c(g)}\Rightarrow ans\frac{1}{n}\sum_{i1}^nn^{(n,i)}∣X/G∣∣G∣1∑g∈Gmc(g)⇒ansn1∑i1nn(n,i)。
第 iii 种置换的循环节个数为 gcd(n,i)\gcd(n,i)gcd(n,i)。
这个环只能顺时针/逆时针转动不妨考虑顺时针那么转 0∼n−10\sim n-10∼n−1 个元素就对应不同的置换共 nnn 种。
假设当前环的开头为 xxx在第 iii 种置换下有 x→xi→x2i→⋯→xx\rightarrow xi\rightarrow x2i\rightarrow\dots\rightarrow xx→xi→x2i→⋯→x。
假设在 xkixkixki 回到开头则 x≡xki(modn)⇒ki≡0(modn)⇒kngcd(n,i)x\equiv xki\pmod n\Rightarrow ki\equiv 0\pmod n\Rightarrow k\frac{n}{\gcd(n,i)}x≡xki(modn)⇒ki≡0(modn)⇒kgcd(n,i)n
这个 kkk 恰好就是环长度所以个数为 n/kgcd(i,n)n/k\gcd(i,n)n/kgcd(i,n) 1n∑i1nn(n,i)1n∑d1n∑i1nnd[(n,i)d]∑d∣n∑i1nnd−1φ(nd)\frac{1}{n}\sum_{i1}^nn^{(n,i)}\frac{1}{n}\sum_{d1}^n\sum_{i1}^nn^{d}[(n,i)d]\sum_{d\mid n}\sum_{i1}^nn^{d-1}\varphi(\frac nd) n1i1∑nn(n,i)n1d1∑ni1∑nnd[(n,i)d]d∣n∑i1∑nnd−1φ(dn) 可以在 O(n)O(\sqrt n)O(n) 时间内枚举所有因数 ddd。
预处理 1e61e61e6 以内的 φ\varphiφ后面的就 n\sqrt{n}n 暴力算。
#include cstdio
#define maxn 1000005
int mod, cnt;
bool vis[maxn];
int prime[maxn], phi[maxn];void sieve( int n 1e6 ) {phi[1] 1;for( int i 2;i n;i ) {if( ! vis[i] ) prime[ cnt] i, phi[i] ( i - 1 );for( int j 1;j cnt and 1ll * i * prime[j] n;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {phi[i * prime[j]] phi[i] * prime[j];break;}else phi[i * prime[j]] phi[i] * phi[prime[j]];}}
}int qkpow( int x, int y ) {x % mod;int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}int PHI( int x ) {if( x 1e6 ) return phi[x] % mod;int ans x;for( int i 2;i * i x;i )if( x % i 0 ) {ans ans / i * ( i - 1 );while( x % i 0 ) x / i;}if( x ^ 1 ) ans ans / x * ( x - 1 );return ans % mod;
}int main() {sieve();int T, n;scanf( %d, T );while( T -- ) {scanf( %d %d, n, mod );long long ans 0;for( int i 1;i * i n;i ) {if( n % i ) continue;if( i * i n ) (ans qkpow(n, i - 1) * PHI(n / i) % mod) % mod;else(ans qkpow(n, i - 1) * PHI(n / i) % mod qkpow(n, n / i - 1) * PHI(i) % mod) % mod;}printf( %lld\n, ans );}return 0;
}
