动态规划（DP）
树形DP
数学
位运算
异或
异或前缀和
\( s(n)为1到n的数的异或和 \)
\( s(n) = \begin{cases} 1 , ~~~ n \% 4 == 1 \\ 0 , ~~~ n \% 4 == 3 \\ n , ~~~ n \% 4 == 0 \\ n + 1 , ~~~ n \% 4 == 2 \\ \end{cases} \)
代码实现如下：
auto xorprefix = [&](ll n) {
int flag = n % 4;
if (flag == 0) {
return n;
} else if (flag == 1) {
return 1;
} else if (flag == 2) {
return n + 1;
} else if (flag == 3) {
return 0;
}
};
数论
简化公式
\( \sum\limits_{k = 1}^{n} k = \frac{n(n + 1)}{2} \)
\( \sum\limits_{k = 1}^{n} k^{2} = \frac{n(n + 1)(n + 2)}{6} \)
\( \sum\limits_{k = 1}^{n} k^{3} = (\sum\limits_{k = 1}^{n} k)^{2} = \frac{ n^{2} (n + 1)^{2} }{4} \)
裴蜀定理
\( 对于二元方程ax + by = c \)
\( 当且仅当c = gcd(a , b)时 \)
\( x , y 存在整数解 \)
\( 当c \neq gcd(a , b) \)
\( x , y 不存在整数解，但有非整数解 \)
推广：
\(
一定存在整数x , y , 满足ax + by = gcd(a , b) * n
\)
再推广:
\(
一定存在整数\{ x_{i} \vert i \in [1 , n] \},满足
\)
组合数学
排列组合
二项式定理
\[(x + y)^{a} = \sum\limits_{k = 0}^{\infty} C_{a}^{k} x^{k} y^{a - k} \]\(\tbinom{n}{m} = C_{n}^{m}\)
容斥原理
例题：求分母不超过n的所有最简真分数的个数与他们的和 (n <= 1e6)
显然有:
\( ans = \sum\limits_{a = 1}^{n} \sum\limits_{b = 1}^{a} ([b < a] * [gcd(a , b) == 1]) \)
\( = (\sum\limits_{a = 1}^{n} \sum\limits_{b = 1}^{n} [gcd(a , b) == 1]) / 2 \)
那么只需求出n以内的互质对即可。即以1为最大公约数的数对
由容斥原理可以得知，先找到所有以1为公约数的数对，再从中剔除所有以1的倍数为公约数的数对，余下的数对就是以1为最大公约数的数对。即f(k)=以1为公约数的数对个数 - 以1的倍数为 公约数 的数对个数。
如此，最简真分数的个数就求好了，还需求出它们的和。
可以注意到，当(x,y)为互质时，(y-x,y)也互质。
那么有这些最简真分数的和就是它们的个数除以2。
代码实现如下：
ll nn = 2e6;
cin >> nn;
vector<ll> f(nn + 1);// f[i] 表示 gcd == i 的情况有几种
for (ll k = nn; k >= 1; k--) {
f[k] = (nn / k) * (nn / k);//以k为公约数的数对
for (ll i = k + k; i <= nn; i += k) { //减去以k的倍数为公约数的数对
f[k] -= f[i];
}
}
ans1 = f[1] / 2;
ans2 = (double)ans1 / 2.0;
cout << ans1 << " " << ans2 << "\n";
卡特兰数
通项公式：
\[(1) H_{n} = C_{2n}^{n} - C_{2n}^{n - 1} \]\[(2) H_{n} = \frac{1}{n + 1} C_{2n}^{n} \]递推公式:
\[(3) H_{n} = \frac{4 n - 2}{n + 1} H_{n - 1} \]Catalan 特征：
从(0,0)到(n,n)，不越过对角线，即任何时候，向上走的步数不能超过向右走的步数。
一种操作数不能超过另一种操作数，或者两种操作数不能有交集，这些操作的方案数通常是卡特兰数
Catalan 应用：
1.一个有n个0和n个1组成的字串，且所有的前缀字串满足1的个数不超过0的个数。这样的字串个数是多少？
2.包含n组括号的合法运算式的个数有多少？
3.一个栈的进栈序列为1,2,3,~,n，有多少个不同的出栈序列？
4.n个结点可构造多少个不同的二叉树？
5.在圆上选择2n个点，将这些点成对连接起来使得所得到的n条弦不相交的方法数？
6.通过连结顶点而将n+2边的凸多边形分成n个三角形的方法数？
图论(graph)
弦图(chord)
最大独立集
https://oi-wiki.org/graph/chord/?query=最大独立集