排列 1.1不可重排列 1.2可重排列 1.3圆排列 1.4不尽相异元素全排列 1.5多重集的排列

组合 2.1不可重组合数 2.2可重组合 2.3不相邻组合 2.4多重集的组合 2.5常用组合数公式 2.6组合数取模(模板)

常用公式及定理 3.1二项式定理 3.2鸽巢原理 3.3常见恒等式 3.4帕斯卡恒等式 3.5卢卡斯定理推论 3.6容斥原理 3.7错排问题

常见数列及其性质 4.1斐波那契数列 4.2卡特兰数列

递推方程 5.1线性递推方程 5.2非线性递推方程 5.3求解递推方程(模板)

母函数 6.1普通母函数 6.2指数型母函数 6.3整数拆分

Polya计数

快速傅里叶（FFT）

若n和r都是整数，且0{∞*a_1,∞*a_2,.....,∞*a_n}\} {k_1*a_1,k_2*a_2,.....,k_n*a_n}\} {k_1*a_1,k_2*a_2,.....,k_n*a_n}\} {k_1*a_1,k_2*a_2,.....,k_n*a_n}\} {∞* a_1,∞* a_2,.....,∞* a_n}\} {k_1*a_1,k_2*a_2,.....,k_n*a_n}\} {k_1*a_1,k_2*a_2,.....,k_n*a_n}\} 3,D1​=0,D2​=1

F i = F i − 1 + F i − 2 ， F 1 = F 2 = 1 Fi=F_{i-1}+F_{i-2}，F_1=F_2=1 Fi=Fi−1​+Fi−2​，F1​=F2​=1的数列 { F n } \{{F_n}\} {Fn​}称为斐波那契数列， F n F_n Fn​为斐波那契数

F n ≡ 276601605 ( 69150401 3 n − 30849599 7 n ) ( m o d ( 1 e 9 + 9 ) ) Fn ≡ 276601605(691504013^n -308495997^n)(mod (1e9+9)) Fn≡276601605(691504013n−308495997n)(mod(1e9+9)) 由二次剩余推导

1.平方与前后项：从第二项开始，每个奇数项的平方都比前后两项之积少1，每个偶数项的平方都比前后两项之积多1 2.与集合子集：Fn+2同时也代表了集合{1,2,…,n}中所有不包含相邻正整数的子集个数 3.奇数项求和： F 1 + F 3 + F 5 + . . . + F 2 n − 1 = F 2 n − F 2 + F 1 F_1+F_3+F_5+...+F_{2n-1} = F_{2n}-F_2+F_1 F1​+F3​+F5​+...+F2n−1​=F2n​−F2​+F1​ 4.偶数项求和： F 2 + F 4 + F 6 + . . . + F 2 n = F 2 n + 1 − F 1 F_2+F_4+F_6+...+F_{2n} = F_{2n+1}-F_1 F2​+F4​+F6​+...+F2n​=F2n+1​−F1​ 5.平方求和： F 1 2 + F 2 2 + . . . + F n 2 = F n ∗ F n + 1 F_1^2 +F_2^2 +...+F_n^2 = F_n*F_{n+1} F12​+F22​+...+Fn2​=Fn​∗Fn+1​ 6.两倍项关系： F 2 n / F n = F n − 1 + F n + 1 F_{2n}/F_n = F_{n-1}+F_{n+1} F2n​/Fn​=Fn−1​+Fn+1​ 7. F ( n − 1 ) ∗ F ( n + 1 ) − F n 2 = ( − 1 ) n F(n-1)*F(n+1)-F_n^2 = (-1)^n F(n−1)∗F(n+1)−Fn2​=(−1)n 8.质数数量： 每3个连续的数中有且只有一个被2整除 每4个连续的数中有且只有一个被3整除， 每5个连续的数中有且只有一个被5整除， 每6个连续的数中有且只有一个被8整除， 每7个连续的数中有且只有一个被13整除， 每8个连续的数中有且只有一个被21整除， 每9个连续的数中有且只有一个被34整除 9.尾数循环：   个位数每60步一循环，后两位数每300步一循环，后三位数，每1500步一循环，后4位数每15000步一循环，后5位数每150000步一循环

h ( n ) = C ( 2 n , n ) / ( n + 1 ) h(n)=C(2n,n)/(n+1) h(n)=C(2n,n)/(n+1) h ( n ) = C ( 2 n , n ) − C ( 2 n , n − 1 ) h(n)=C(2n,n)-C(2n,n-1) h(n)=C(2n,n)−C(2n,n−1)

h ( n ) = h ( 0 ) ∗ h ( n − 1 ) + h ( 1 ) ∗ h ( n − 2 ) + . . . + h ( n − 1 ) ∗ h ( 0 ) ( n > = 2 ) h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2) h(n)=h(0)∗h(n−1)+h(1)∗h(n−2)+...+h(n−1)∗h(0)(n>=2) h ( n ) = h ( n − 1 ) ∗ ( ( 4 ∗ n − 2 ) / ( n + 1 ) ) h(n)=h(n-1)*((4*n-2)/(n+1)) h(n)=h(n−1)∗((4∗n−2)/(n+1))

卡特兰数的应用都可以归结到一种情况：有两种操作，分别为操作一和操作二，它们的操作次数相同，都为 N，且在进行第 K 次操作二前必须先进行至少 K 次操作一，问有多少中情况？结果就Catalan(N)。

1.给定n个数，有多少种出栈序列 2.n个结点的二叉树有多少种构型 3.有 n + 1 n+1 n+1个叶子的满二叉树的个数 4.在 n ∗ n n*n n∗n的格子中，只在下三角行走，每次横或竖走一格，有多少种走法 5.将一个凸n+2边型剖分成三角形的方法数 6.在圆上选择2n个点，将这些点成对相连使得到的n条线段不相交的方法数 7.n个长方形填充一个高度为n的阶梯状图形的方法数 8.由n个+1和n个-1组成的排列中，满足前缀和>=0的排列数 9.括号化问题，左括号和右括号各有n个时，合法的括号表达式的种类 10.有n+1个数连乘，乘法顺序的种类 11.n位二进制中，有m个0，其余为1，有h[C(n,m)-C(n,m-1)]种 12.将有2n个元素的集合中的元素两两分为n个子集，若任意两个子集都不交叉，那么我们称此划分为一个不交叉划分。此时不交叉的划分数是Catalan(N) 13.n层的阶梯切割为n个矩形的切法数也是Catalan(N)。 14.在一个 2 ∗ n 2*n 2∗n的格子中填入1到2n这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数也是Catalan(N)。