黑科技系列

Catalan数

1 2 5 14 42 132

通项公式：$\frac{C(2n, n)}{n + 1}$

判断$d$是否是子串的循环节

若询问区间为$(l, r)$，则只需判断$(l + d, r)$和$(l, r - d )$是否相同

证明：不断归纳即可

$n$个数两两相乘的结果

设$a_i$表示第$i$个元素

则$$\sum a_i * a_j  = (\sum a_i) ^2 - \sum{a_i ^ 2}$$

$O(n)$求组合数

若模数是质数：递推出阶乘和阶乘的逆元。

若模数不是质数：线性筛出每个元素的最小质因数，不断的把每个数分解

被$a$的整除性质

被$4$整除

末两位能被4整除

被$8$整除

若数字的后三位能被$8$整除，则该数字能被$8$整除

证明

设$x = 10000 * a_i + 1000 * a_{i - 1} + \dots$

发现大于$3$的位都会分解出$8$这个因数

被$6$整除

能被6整除必然同时可被2和3整除，因此特点为:"各位数字之和是3的倍数的偶数."