1、每一次有意义的取模至少会使结果减少一半。

2、找一个数之后第一个比他小的数， $ST$ 表 $+$ 二分。

3、 $ax+by=c$ 通解：

​ $\frac{a}{g}x_0+\frac{b}{g}y_0=1$ ，

​ $x=x_0\times \frac{c}{g}+t\times\frac{b}{g}$ ， $y=y_0\times \frac{c}{g}-t\times \frac{a}{g}$

3、线性求逆： $(ab)'=a'b'(mod\text{ }p)$ ，求出所有质数对 $p$ 的逆，线性筛。

4、 $\lfloor\lfloor a/b\rfloor/c\rfloor=\lfloor a/(b\times c)\rfloor$ ， $\lceil a/b\rceil=\lfloor (a+b-1)/b\rfloor=\lfloor (a-1)/b\rfloor+1$

5、 $(ag)\%(bg)=(a\%b)\times g$ ， $(a\%(bc))\%c=a\%c$

6、组合数取模，通过 $CRT$ 转化为求多个 $mod\text{ }pi^k$ 的值，预处理 $M!$ 的逆元

7、错位排列数： $D_0=1,D_1=0,D_n=(n-1)\times(D_{n-1}+D_{n-2})$

8、贝尔数， $n$ 个可区分物体划分成若干不可辨别集合方案数，第二类斯特林数的前缀和， $\begin{align}B_{n+1}=\sum_{k=0}^{n} C(n,k)\times B_k\end{align})$ ，考虑 $n+1$ 和哪 $n-k$ 个物品放在一起。

9、卡塔兰数：出栈序列方案数 $\to$ 枚举最后一个出栈的。括号序列 $\to$ 翻转第一个不合法前缀。

10、除法分块： $O(\sqrt N)$ 。

$\begin{align}\sum_{i=1}^n\lfloor n/i\rfloor\end{align}$ ：

for(int i = 1;i <= n;i = n / (n / i) + 1)

{//i~n/(n/i)

    ans += n / i * (n / (n / i) - i + 1);

}

$\begin{align}\sum_{i=1}^n n\%i=\sum_{i=1}^n n-i\times \lfloor n/i\rfloor\end{align}$

11、 $\begin{align}\sum_{i=1}^n gcd(i,n)=\sum_{d|n}d\times\phi(\frac{n}{d})\end{align}$

void dfs(int n,int i,int phi)

{

    if(i == cnt + 1)

    {

        ans += phi * n;

        return;

    }

    for(int j = 0;j <= q[i];++j)

    {

        dfs(n * power(pi[i],j),i + 1,phi * power(p[i],j - 1) * (p[i] - 1));

    }

}

$O(\sqrt N)$

12、巴什博弈： $mod\text{ }(m+1)=0$

13、 $CHOMP$ 博弈：选右上角，如果要输就选别人下一步要选的。

14、尼姆博弈：异或和为零，由于最开始异或和为零所以一定存在一个数变小后使异或和为零。