1.异或

对于 $x,y,z(x<y<z)$，$min{x xor y,y xor z}<x xor z$。
$a ^ a ^ b = b，a ^ a = 0，a ^ b ≤ a + b$

2.组合数学相关

写了一上午组合数学要吐了\kel
1.$k \times C_{n}^{k}= n \times C_{n-1}^{k-1}$ 有$n$个人，要选择其中$k$个人组成一支小队，从中再选出一个队长，不难发现等式两边都适用于这个问题
即$C_{n}^{k}= \frac{n}{k} C_{n-1}^{k-1}$
2.$\sum_{i=0}^{n} C_{n}^{i}=2^{n}$ 枚举子集的角度考虑来证明
3.$C_{n+m}^{m}=\sum_{i=0}^{n} C_{n}^{i} \times C_{m}^{m-i}$ 考虑从集合$A（有$n$个元素）和集合$B$（有$m$个元素）中选择$m$个元素，容易发现等式两边是问题的不同表达
4.$C_{2n}^{n}=\sum_{i=0}^{n} C_{n}^{i} \times C_{n}^{i}$上式$m=n$的情况
5.$\sum_{i=0}^{n}C_{m}^{i}=C_{m+1}^{n+1}$ 右式：在$0-n$中选择$m+1$个数 左式：设当前最大值为$i$,有多少种可能？
左式是把右式按照最大值分类统计后的结果，故两者相等

3.树形dp状态设计的小技巧

dp[i][0/1] $0/1$ 可以表示有向边的方向 方向也是dp中可以量化的量

4.LIS

刚刚发现自己不会LIS的带log写法
其实就是设$f[i]$表示长度为$len$的LIS的结尾的当前最大值。然后二分查找最小值之后第一个小于最小值的数就行了。

    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = t + 1;
        while (r - l > 1)
        {
            int m = l + (r - l) / 2;
            if (f[m] >= h[i]) 
                l = m;
            else 
                r = m;
        }
        int x = l + 1;
        if (x > t) 
            t = x;
        f[x] = h[i];
    }
    cout << t << "\n";