参考博客 抽屉原理（鸽巢原理） 第一抽屉原理 定理1： 把n+1件东西放入n个抽屉，则至少有一个抽屉里会放入两件或两件以上的东西。 定理2： 从另一个角度考虑，把n-1件东西放入n个抽屉，则至少一个抽屉是空的。 定理3：…

行列式 其中j_1j_2...j_n是n元排列 r(j_1j_2...j_n)表示其中的逆序对个数 上三角行列式 主对角线下方全为0的n阶行列式称为上三角行列式 上三角行列式的值为对角线上n个元素的乘积 性质一： 交换行…

矩阵 由n \times m个数排成n行，m列的一张表称为一个n \times m矩阵。 矩阵中的每一个数称为这个矩阵的一个元素 矩阵的第i行和第j列交叉位置的元素称为矩阵的(i,j)元 若一个矩阵的行与列相等，则称为它…

写在最前：参考博客 公平组合游戏ICG 若一个游戏满足： - 由两名玩家交替行动 - 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关 - 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定…

对于莫比乌斯反演只需记住： \left[ gcd\left( i, j \right) =1 \right] =\sum_{d|gcd\left( i,j \right)}{\mu \left( d \right)} 例…

参考博客 裴蜀定理 设a,b是不全为0的整数，存在无穷多对整数(x,y)，满足不定方程ax+by=d,其中d=gcd(a,b)，即ax+by=gcd(a,b) 推论1： gcd(a,b)=d \Leftrightarro…

写在最前：参考博客 整数的取余运算（模运算） 定义：带余除法，设a，b是整数，且b>0，使得a=bq+r,称q为商，r为余数。 定义以运算： 1. 取模运算: a\ mod \ p 2. 模p加法: (a+b)\ mod…

容斥原理 基本思想：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后把计数时重复计数的数目排斥出去，使得计算结果无遗漏又无重复。 一句话：奇加偶减 A\bigcup_{}{B}\bigcup_{}{C…

极性函数 如果a,b互质时，满足f\left( ab \right) =f\left( a \right) f\left( b \right)的函数f称为极性函数。 欧拉函数 对正整数n，欧拉函数是小于n的正整数中与n互…

基本性质定理： fib_{n} = 0 \ (n=0) fib_{n} = 1 \ (n=1) fib_{n} = fib_{n-1}+fib_{n-2} \ (n>1) 性质1： \sum_{i=1}^n{f_i=f_…