[莫名其妙的]二项式反演

\text{第一反演公式}

\text{设}n\in \mathbb{N}_+\,\,,\text{多项式序列}\left\{ p_n \right\} ,\left\{ q_n \right\} \text{有如下关系:}

p_n\left( x \right) =\sum_{k=0}^n{\alpha _{nk}q_k\left( x \right) \,\,},\,\,q_n\left( x \right) =\sum_{k=0}^n{\beta _{nk}p_k\left( x \right)}

\text{且}A=\left( \alpha _{ij} \right) ,B=\left( \beta _{ij} \right) \text{为非奇异矩阵},\,\text{则有}

v_n=\sum_{k=0}^n{\alpha _{nk}u_k}\Leftrightarrow u_n=\sum_{k=0}^n{\beta _{nk}v_k}

 

 

Proof.

\text{令}p=\left( p_0,p_1,\cdots ,p_n \right) ^T,q=\left( q_0,q_1,\cdots ,q_n \right) ^T

u=\left( u_0,u_1,\cdots ,u_n \right) ^T,v=\left( v_0,v_1,\cdots ,v_n \right) ^T

\text{则可将原式表示为}

p=Aq\,\,,\,\,q=Bp

\therefore p=Aq=ABp.

\because p\text{是线性空间}R\left[ x \right] \text{的一组基}

\therefore AB=I,\,\,A^{-1}=B

\therefore v=Au\Leftrightarrow u=A^{-1}v=Bv\,\,\,\,\blacksquare

 

 

\text{二项式反演}

\text{设}\left\{ a_n \right\} \text{和}\left\{ b_n \right\} \text{是两个数列}

a_n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) b_k}\Leftrightarrow b_n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) a_k}

 

 

Proof.

x^n=\left( 1+x-1 \right) ^n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) \left( x-1 \right) ^k}

\left( x-1 \right) ^n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) x^k}

\text{由第一反演公式可得证}

[咕咕]OI实用群论

\text{群}\left( G,\cdot \right)

\text{封闭性:\ }\forall a\in G,b\in G,a\cdot b\in G

\text{结合律:\ }\left( a\cdot b \right) \cdot c=a\cdot \left( b\cdot c \right)

\text{幺元}\left( \text{单位元} \right) :\ \exists e\in G,\ \text{s.t}.\forall a\in G,\ e\cdot a=a\cdot e=a

\text{逆元:\ }\forall a\in G,\ \exists b\in G,\ \text{s.t.\ }a\cdot b=b\cdot a=e

 

\text{所有行列式非零的}n\text{阶方阵是一个群}

\text{群中的单位元唯一}.

\text{证明:\ }

\text{设有两个单位元}e_1,e_2

e_1=e_1e_2=e_2.\ \blacksquare

\text{群中的逆元唯一}

\text{证明:}

\text{设}a\text{有两个逆元}b,c

b=b\cdot \left( a\cdot c \right) =\left( b\cdot a \right) \cdot c=c.\ \blacksquare

 

\text{周期:\ }a\text{的周期是}o\left( a \right)

o\left( a \right) \text{表示最小正整数,\ 使得}a^{o\left( a \right)}=e

 

\left( ab \right) ^{-1}=a^{-1}b^{-1}

 

\text{子群:}

\text{若}\left( G,\cdot \right) ,\ H\subseteq G,\ \text{且}\left( H,\cdot \right) \text{是群,\ 称在运算}\cdot \text{下}H\text{是}G\text{的子群,\ 用}H\leqslant G\text{表示}.

 

\text{生成子群}

\text{集合}S\text{的生成子群用}<s>\text{表示}.

 

\text{右傍集:}

\text{如果}H\leqslant G,\ \text{对于}a\in G,\ \text{定义集合}Ha=\left\{ x\in G\ |\ \exists h\in H,ha=x \right\}

 

Ha=Hb\text{当且仅当}ab^{-1}\in H

\text{若}Ha=Hb,\ ea\in Ha,\ \text{即}a\in Hb,\ \text{那么}\exists h\in H,\ a=hb,\ ab^{-1}=h.

\text{若}ab^{-1}\in H,\

ha=ha\left( bb^{-1} \right) =h'b\in Hb,\ \text{因此}Ha\subseteq Hb.

hb=hb\left( a^{-1}a \right) =h\left( ab^{-1} \right) ^{-1}a\in Ha,\ \text{因此}Hb\subseteq Ha

\text{因此}Ha=Hb.\ \blacksquare

 

\text{若}Ha\ne Hb,\ \text{那么}Ha\cap Hb=\varnothing

\text{证明:\ }

\text{假设}x\in Ha\cap Hb,\ \text{则}\exists h_1,h_2\in H,\ h_1a=h_2b=x,\

\text{那么}a=h_{1}^{-1}h_2b,\ ab^{-1}=h_{1}^{-1}h_2\in H,\ Ha=Hb,\ \text{矛盾}.\blacksquare

 

\text{傍集是无交集的,\ 每个傍集都是和}H\text{一样大的,\ 即|}H|=|Ha|

 

\text{由于}\forall g\in G,\ g\in Hg,\ \text{所以}G\text{中每个元素都在某个傍集中}.

\text{用}\left[ G:H \right] \text{表示不同的傍集数,\ 则|}G|=|H|\cdot \left[ G:H \right]

|H|\text{是|}G|\text{的约数}.

 

\text{若}a\in G,\text{则}o\left( a \right) \ |\ |G|

\text{证明:\ 考虑}a\text{的生成子群}<a>=\left\{ a,a^2,a^3\cdots a^{o\left( a \right)} \right\}

 

|Ha|=|H|

\Rightarrow \text{如果}h_1\ne h_2,\ \text{那么}h_1a\ne h_2a

\text{证明:\ 若}h_1a=h_2a,\ h_1aa^{-1}=h_2aa^{-1},\ h_1=h_2\text{矛盾}

\therefore \text{对于不同的}h,\ ha\text{互不相同,\ 因此|}Ha|=|H|.\ \blacksquare

 

\text{P.S.费马小定理的另一个证明}

\text{考虑质数}p\text{和群}G=\left\{ \text{1,2,}\cdots p-1 \right\} ,\ \text{群的运算定义为mod\ }p\text{意义下的乘法}.

\forall a\in G,\ a^{o\left( a \right)}=e;\ o\left( a \right) |\left( p-1 \right)

\therefore a^{p-1}=\text{1.\ }\blacksquare

\text{欧拉定理证明}

\text{考虑}n\in N^+,\ \text{考虑群}G=\left\{ x\ |1\leqslant x\leqslant n,\ gcd\left( x,n \right) =1 \right\}

|G|=\varphi \left( n \right) ,\ o\left( a \right) \ |\ |G|

\therefore \forall a\in G,a^{\varphi \left( n \right)}=\text{1\ }\left( \text{mod\ }n \right) .\ \blacksquare

 

\text{给定}a,b,\ o\left( a \right) =m,o\left( b \right) =n,\ ab=ba

\text{证明:\ 若}\left( m,n \right) =\text{1,\ 则}\exists g\in G,\ \text{s.t.\ }o\left( g \right) =mn

g=a\cdot b,\ \left( ab \right) ^{mn}=e,\ \text{设}o\left( g \right) =k\leqslant mn

\text{若}\left( ab \right) ^k=e,\text{那么}a^{nk}=\left( ab \right) ^{nk}=e,\ \text{可知}m|nk

\text{同理}n|mk.

\because \left( m,n \right) =1

\therefore m|k,\ n|k,\ mn|k,\ k=mn.\ \blacksquare

 

\text{证明:\ }\exists g\in G,\ \text{s.t.\ }o\left( g \right) =\text{lcm}\left( m,n \right)

m=\prod_{i=1}^s{t_{i}^{p_i}},\ n=\prod_{i=1}^s{t_{i}^{q_i}}

\text{通过交换各个}a_i\text{的顺序,\ 总能存在}0\leqslant l\leqslant s,\ \text{s.t}.

\forall i\leqslant l,\ p_i\leqslant q_i;\ \forall i>l,\ p_i\geqslant q_i

\text{令}c=a^u,\ u=\prod_{i=1}^l{t_{i}^{p_i}};\ d=b^v,\ v=\prod_{i=l+1}^s{t_{i}^{q_i}}

o\left( cd \right) =\text{lcm}\left( m,n \right)

\text{由于}o\left( c \right) =\frac{m}{u}=v;\ o\left( d \right) =\frac{n}{v}=u

\text{那么gcd}\left( o\left( c \right) ,o\left( d \right) \right) =\text{1,\ 又}cd=dc,\ \text{由}\left( 1 \right) \text{可得}o\left( cd \right) =o\left( c \right) o\left( d \right) =\text{lcm}\left( c,d \right) .\ \blacksquare

 

\text{如果}G=<a>,\ \text{称}G\text{为循环群}.

\text{若}G\text{为有限循环群,\ 则}o\left( a \right) =|G|

 

\text{令}k=o\left( a \right) ,\ \text{则}a^k=e,\ \text{那么}a^{k+i}=a^i

 

\left\{ a^1,\ a^2,\ \cdots ,\ a^k \right\} ,\ \text{这当中的数两两不同}

\text{反证:\ 设}1\leqslant x\leqslant y\leqslant k,\ a^x=a^y,\ \text{那么}a^{y-x}=e,\ \text{矛盾.\ }

 

\text{e.g.\ mod\ 7意义下的乘法下,}\left\{ \text{1,2,3,4,5,}6 \right\} \text{是循环群}.

 

G\text{是循环群当且仅当|}G|\text{是最小的}m\in N^+,\ \text{使得}\forall g\in G,\ g^m=e

\text{证明:}

\text{若}G=<a>\text{是循环群,\ 则}o\left( a \right) =|G|,\ \therefore m\geqslant |G|

\text{又}\because \forall g\in G,g^{|G|}=e,\ \therefore m=|G|

\text{若}m=|G|

\text{如果}\exists a\in G,\ \text{s.t.\ }o\left( a \right) =|G|,\ \text{那么}G=<a>

\text{否则,\ }\forall g\in G,\ o\left( g \right) <|G|

\text{设周期最大的元素为}a,\ o\left( a \right) =t

\therefore \forall g\in G,\ \text{由上述性质可得}o\left( g \right) |t

\text{那么}t\text{满足}\forall g\in G,g^t=e,\ m\leqslant t,\ \text{矛盾.\ }\blacksquare

 

\text{半群:\ 满足封闭性和结合律}

\text{交换群:\ 满足交换律的群}

\text{环:\ }\left( R,+,\cdot \right) ,\ \text{其中}\left( R,+ \right) \text{是交换群,\ }\left( R,\cdot \right) \text{是半群}

\text{e.g.\ }\mathbb{Z}\ \mathbb{R}\left[ \text{x} \right] \

\text{域:\ }\left( F,+,\cdot \right) ,\ \text{其中}\left( F,+ \right) \text{是交换群,\ }\left( F\backslash \left\{ 0 \right\} ,\cdot \right) \text{是交换群}

\text{e.g.\ }\mathbb{Q}\ \mathbb{R}\ \mathbb{C}

 

\text{代数基本定理:\ 在域}F\text{中,\ }n\text{次非零多项式}f\left( x \right) \text{至多有}n\text{个不同的根}.

\text{证明留作习题}.

 

\text{任意一个域的乘法群的有限子群}G\text{一定是循环}.

\text{证明:}

\text{令}m\text{是最小的正整数,\ 使得}\forall g\in G,\ g^m=e

\text{首先}\forall g\in G,\ g^{|G|}=e,\ m\leqslant |G|

\text{考虑多项式}x^m-e,\ G\text{中元素都是这个多项式的根;}

\text{由代数基本定理,\ |}G|\leqslant m

\therefore m=|G|

\text{由循环群性质得,\ }G\text{是循环群.\ }\blacksquare

 

\text{考虑质数}p,\ \text{在对}p\text{取模的意义下进行加法和乘法,\ 那么}G=\left\{ \text{0,1,2,}\cdots ,p-1 \right\} \text{是一个域}

\text{乘法群}G\backslash \left\{ 0 \right\} \text{是循环群}

\text{循环群的生成元叫做原根}.

\text{生成元:\ 设}a\text{为群}G\text{的生成元,\ 则}G=<a>.

 

\text{对于原根}a,\ \forall 1\leqslant i\leqslant p-\text{1,\ }\exists x>\text{0,\ }a^x=i\ \left( \text{mod\ }p \right)

 

\text{一个循环群}G,\ \text{设}p-1=|G|,\ \text{其中}p\text{为质数}.

\text{设}a\text{为生成元,}

G=\left\{ a,a^2,a^3,\cdots ,a^{p-1} \right\}

\text{那么}a^{p-1}=e;

\text{如果}g\text{是原根,\ 当且仅当}o\left( g \right) =p-1.

\text{设}g=a^t,\ \text{那么}o\left( g \right) \text{为最小的}s\text{使得}\left( p-1 \right) |st

 

o\left( g \right) =p-\text{1当且仅当gcd}\left( t,p-1 \right) =1

\because \left( p-1 \right) |st,\ \text{且}t|st

\therefore st\text{是}t\text{和}p-\text{1的公倍数}

\text{若gcd}\left( p-\text{1,}t \right) =\text{1,\ 那么lcm}\left( p-\text{1,}t \right) =t\left( p-1 \right)

\text{由于}st\text{是}t\text{和}p-\text{1的公倍数,\ 因此}s=p-1

\text{若gcd}\left( p-\text{1,}t \right) \ne \text{1,\ 设gcd}\left( p-\text{1,}t \right) =d,\ \text{则}d>1

\text{取}s=\frac{p-1}{d},\ \text{则}st=\left( p-1 \right) \frac{t}{d}

 

|G|\text{中原根的数量为}\varphi \left( p-1 \right)

\text{找原根:\ 由于}\varphi \left( p-1 \right) \text{较大,\ 暴力枚举2,3,}\cdots \text{并判断}.

\text{判断:\ 只需判断是否存在比}p-\text{1小的数}x\text{使得}a^x=1

\text{枚举}p-\text{1的所有质因子}d,\text{判断}a^{\frac{p-1}{d}}\text{是否为}1

\text{如果都不是,\ 那么}a\text{就是原根}.

\because \text{假设}o\left( a \right) =k,\ \text{假设}k<p-\text{1,\ 那么}k|p-1

\text{证明:}

\text{由于}a^{\text{gcd}\left( k,p-1 \right)}=\text{1,\ 所以}k|p-\text{1.\ }\blacksquare

\text{令}t=\frac{p-1}{k},\ \text{那么}t>1

\text{令}d\text{是}t\text{中任一质因子,\ }\frac{p-1}{t}|\frac{p-1}{d},\ \text{那么}a^{\frac{p-1}{d}}=1

 

\text{离散对数}

\text{记}G\text{的原根是}a,\ \text{由于}\forall g\in G,\ \exists t,a^t=g,\ \text{那么}t=\log _ag

 

\left( \text{BSGS} \right) \text{令}q=\lceil \sqrt{p} \rceil

\text{求出}S=\left\{ a^0,a^1,\cdots ,a^q \right\}

T=\left\{ a^0,a^q,a^{2q},\cdots a^{q^2} \right\}

\forall a^x=g,\ \text{因为}x=kq+l,\ 0\leqslant k,l\leqslant q

\text{那么}g=a^{kq}a^l

\text{可以写成}g=st,s\in S,t\in T

 

\text{枚举}s\in S,\ \text{需要的}t\text{就是}s^{-1}g.

\text{对}T\text{建哈希表,\ 查找}s^{-1}g\text{在}T\text{内是否存在}.

O\left( \sqrt{p} \right) \text{求一个离散对数}x.

乱写点线代

UPD:刚买了本线代,感觉还挺好的,学几页之后会在这里补充一些想法和笔记。

 

矩阵都会吧……基础的加减法

矩阵转置满足:

\begin{array}{l} \left( A^T \right) ^T=A \\\\ \left( \lambda A \right) ^T=\lambda A^T \\\\ \left( AB \right) ^T=B^TA^T \\\\ \end{array}


矩阵乘法(提高组内容)

\begin{array}{l} C_{mn}=A_{mp}\times B_{pn} \\ C_{ij}=\sum_{k=1}^p{a_{ik}b_{kj}} \\ \end{array}


一些常见的规律

\begin{array}{l} A\left( BC \right) =\left( AB \right) C \\ \left( A+B \right) C=AC+BC \\ C\left( A+B \right) =CA+CB \\ \lambda \left( AB \right) =\left( \lambda A \right) B=A\left( \lambda B \right) \\ \end{array}


Hadamard积

没见过这玩意

以下是运算定义

\left( A\ast B \right) _{ij}=a_{ij}b_{ij}


Kronecker积

神奇。

\left( \begin{matrix} 1& 2\\ 3& 4 \end{matrix} \right) \otimes \left( \begin{matrix} 5& 6\\ 7& 8 \end{matrix} \right) =\left( \begin{matrix} 1\cdot 5& 1\cdot 6& 2\cdot 5& 2\cdot 6\\ 1\cdot 7& 1\cdot 8& 2\cdot 7& 2\cdot 8\\ 3\cdot 5& 3\cdot 6& 4\cdot 5& 4\cdot 6\\ 3\cdot 7& 3\cdot 8& 4\cdot 7& 4\cdot 8 \end{matrix} \right)


一个n阶的行列式的定义是这样的

\det \left( A \right) =\sum_{\left( i_1i_2i_3\cdots i_n \right)}{\delta \left( i_1i_2i_3\cdots i_n \right) a_{1i_i}a_{2i_2}a_{3i_3}\cdots a_{ni_n}=|A|}

其中\delta \left( i_1i_2i_3\cdots i_n \right)

表示排列\left( i_1i_2i_3\cdots i_n \right)中当逆序对个数为t\left(-1\right)^{t}的值


好了,我们考虑一些性质

1.\det \left( A \right) =\det \left( A^T \right)

2.两行互换,行列式变号

3.一行乘上k , 行列式乘上k

4.两个行列式只有一行不同,他们的行列式和等于不同的行相加后的行列式

也记为:若行列式的某一列(行)的元素都是两数之和,则这个行列式是对应两个行列式的和

推论:将行列式的任意行乘以实数k,再相应地加到另一行上去,行列式的值不变

证明推论:拆成两个行列式的和,一个有两行成比例…

5.每行每列和均为0的矩阵行列式为0

·   ·   ·   ·   ·

\det \left( AA^T \right) =\left( \det \left( A \right) \right) ^2


Binet-Cauchy公式

A,B分别为n\times ss\times n矩阵

则有\det \left( AB \right)=

\begin{cases} \text{0\ ,\ }n>s\\ \det \left( A \right) \cdot \det \left( B \right) \ ,\ n=s\\ \sum{\det \left( A_s \right) \det \left( B_s \right)}\ ,n<s \end{cases}

这里面那个A_s通俗的,不严格的定义就是说从A里面s行选任意n行组成的新的矩阵,然后B_s也是类似,最后那个 \sum 就是枚举全部的这样的组合


高斯消元法求解行列式 (在此强烈安利 ATP学姐的高斯消元 )

高斯消元这玩意都会吧……

这儿有些细节

第一是交换两行的时候要对答案取负

第二是要用第j行去减第i行,所得答案作为新的第j行(也就是这里的减法正好相反)

最后求 \det \left( A \right) ,因为根据行列式的定义,recur下去每行只能选主对角的那个(否则一定有一个0)那么就是主对角的乘积。(记得取负之类的)


矩阵树定理

非常奇妙

我们来定义图G的度数矩阵D为一个n \times n的矩阵,当结点i \ne j时,d_{ij}=0 ;  当i=j时,d_{ij}等于i的度数

G的邻接矩阵A,当结点i,j之间有k条边相连的的时候,a_{i,j}=k

现在定义图G的Kirchhoff矩阵C=D-A,那么Matrix-Tree定理告诉我们,图G的生成树个数为C的任意一个n-1阶主子式的绝对值。

关于所谓的n-1阶主子式,也就是一个n阶矩阵除第n行和列之后形成的子矩阵的行列式。


Vfk有一篇关于轮状病毒的题解写的特别妙,在这里安利 1002: [FJOI2007]轮状病毒

然鹅他写的好长…… 😕 哇emoji好可爱


矩阵初等变换,先坑着

法法塔也先坑着