前言
学 OI 做的总结，不太算笔记，文本内容尽量规范格式，$\LaTeX$ 公式除了“数学&数论”部分因为没怎么在洛谷上用过一大串的公式所以不太知道规范以外其它内容还算规范吧。但因为这个东西比较历史悠久，极少部分内容会出现格式不规范，马蜂突变等情况。文章分类有点杂，因为都是我学了啥/想到啥，就直接往上写的，用【】框起来的内容表示还没写完（除了能根据上下文得出【】应该填一个形容词的情况以外）。
对拍
这个是对拍，这个也是对拍。对拍能够让你心里有底，至少不会爆零。对拍只能保证你不爆零，不能保证你一定对了。
对拍通常由 4 个程序组成，分别是要对拍的程序，一定对的暴力程序，造数据程序，比较程序。
前两个都很好写，造数据程序一般也好写，但最好可以根据题意整点有强度的数据。比较程序就是模版，背下来就是了：
#include<bits/stdc++.h>
using namespace std;
int main(){
system("g++ -O2 code.cpp -o code -Wall -static -std=c++14");
system("g++ -O2 bl.cpp -o bl -Wall -static -std=c++14");
system("g++ -O2 sj.cpp -o sj -Wall -static -std=c++14");
int t=1e8;
for(int i=1;i<=t;i++){
FILE *fp=fopen("seed.in","w");
fprintf(fp,"%d",i);
fclose(fp);
system("./sj < seed.in > dp.in");
system("./bl < dp.in > dp.ans");
double st=clock();
system("./code < dp.in > dp.out");
double ed=clock();
cout<<i<<" "<<ed-st<<" ms\n";
if(system("diff dp.out dp.ans")){
cout<<"WA\n";
break;
}
}
return 0;
}
值得注意的是，rand 函数随机出的指在 windows 和 linux 下有所不同，windows 下 RAND_MAX=2^15，linux 下 RAND_MAX=2^31-1。以 linux 为例，如果我们想随机出一个小于等于 $2^{62}$ 的数，一种方法是将两个 rand 乘起来，但最后得到的结果并不会均匀的分布在 $[1,2^{62}]$ 之间（越在中间的出现越频繁，而且不难得出偶数出现的次数是奇数的三倍）。正确的做法是将 $2^{62}$ 拆成两个 $2^{31}$ 进行处理，即 ((ll)rand()<<31)|rand()，这样可以保证得到的数是相对均匀的分布在区间范围内的。
STL容器
常用成员函数、语法
front/top 访问第一个元素
back 访问最后一个元素
push/push_back/emplace_back 将元素添加到容器末尾
pop/pop_back 删除容器末尾元素
clear 清空容器
insert/input 插入元素
erase 删除元素
size 返回容器大小
empty 检查容器是否为空
begin/end 返回指向起始/末尾的迭代器
count 返回匹配的元素数量
lower_bound/upper_bound 返回指向首个不小于/大于给定键的元素的迭代器（set,map等有序容器）
for(auto x:v)...
遍历可遍历的容器v
vector
讲一些 vector 的用法。
虽然 vector 常数大，但是因为它的好处太多了，可以让我们忽略掉常数。
首先了解以下 vector 的几个基本的操作的复杂度：
- 随机访问 vector 中的一个元素-常数级
- 在 vector 末尾加入一个元素(push_back或emplace_back)-平均复杂度常数级
- 在任意位置插入或移除元素-与到 vector 结尾的距离成线性 $O(n)$。
以及几个常用/好用的东西：
- 新定义一个长度为 n 的 vector<int>（元素全部为 $0$） ->
vector<int>v(n); - 新定义一个长度为 n 的 vector<int> 并全部初始化为 1 ->
vector<int>v(n,1); - 新定义一个大小为 n*m 的 vector<vector<int>> ->
vector<vector<int>>v(n,vector<int>(m)); - 返回指向起始/末尾的迭代器->
v.begin()与v.end()。 v.size(),v.empty(),v.clear(),v.emplace_back()(push_back的优化)等各种的成员函数。- 两个相同类型的 vector 之间可以进行字典序比较。
那么 vector 有什么好处呢？最主要的一点，也是使我喜欢用 vector 的一点，就是在遇到多测可能忘记初始化，或者变量太多，在函数外部定义容易重名等问题时，我们一般采用尽量将变量定义在需要使用的范围内，不在范围外定义的方法，但这个方法有个缺陷，数组要是不定义在 main 函数外，就需要手动初始化，这又可能出错了。因此我们使用 vector，它可以在任意范围内被定义并默认初始化为 $0$。（当然你可以用 fill(v.begin(),v.end(),1234) 线性时间将 vector 赋值。 ）
还有一点是，开数组时需要开到范围的最大值，定义数组每维的下标必须是个常数，但 vector 不一样，我们可以用多少开多少，需要一个下标从 $1\sim n$ 的数组，使用 vector<int>a(n+1); 即可。不用担心一下子开太大导致 RE 爆零，没有部分分的情况了。
总之，vector yyds。
priority_queue
功能：插入一个元素，用 $O(\log n)$ 的复杂度从大到小排序，如果需要从小到大排序，在入队时将数值取反，出队时取绝对值即可。
定义优先队列 priority_queue<int>p;，暂时用得到的方法都同栈。STL的优先队列默认是给你从大到小排序，如果你想要从小到大排序可以在入队的时候将这个数取反（即 $x$ 变为 $-x$），出队的时候再取个反，当然怕自己写着写着忘了也可以写成：
using tp=tuple<int/*第一关键字*/,int/*第二关键字...*/>;//只要是个可排序的类型就都可以
priority_queue<tp,vector<tp>,greater<tp>>pq;//即可默认从小到大排序
有时我们需要更复杂的比较函数时，就需要重定义小于号了：
struct S{
int x,y;
bool operator<(S a)const{//x从小到大的前提下y从大到小
if(a.x!=x)return a.x<x;
return a.y>y;
}
};
priority_queue<S>pq;
map 与 unordered_map
map 的一些函数：
ma.count(x);查找整个 map 中 x 是否被创建（使用）过，如果你是直接判断 ma[x]===0，map 会自动在容器内创建一个元素 $x$，这会导致如一些 dfs 时，map的空间会炸掉。所以你需要用这个函数来判断 map 中是否存在这个值。
而 map 每次操作的复杂度都是 O(log) 的，当数据范围达到 4e6 时就会 TLE 掉(某些飞鸢在n=9e6时使用了map并T掉了，我不说是谁)。这就令我们很难受，于是，我们就需要用到 unordered_map 了。
unordered_map 的优势自然就是时间复杂度了，他的底层实现是 hash，所以他每次操作的复杂度就取决于 hash 函数的复杂度。一般情况下，我们 hash 函数的复杂度都是 O(1) 的，这就非常的不错了。
至于 hash 函数，部分数据类型都有已经写好的 hash 函数，对于这些类型，unordered_map 的使用方法就与 map 是一样的了。
但是有时我们的关键字是自定义类型（如 struct）或者 C++ 没写他的 hash 函数（如 struct S{unsigned int x,y;};），这种情况下我们就需要自己手写 hash 函数了。以下是一个示例：
struct S{
unsigned int x,y;
bool operator==(S a)const{
return x==a.x&&y==a.y;
}
};
struct SHash{
ull operator()(S a)const{
return (a.x<<32)+a.y;
}
};
unordered_map<S,int,SHash>ma;
当然，你要尽量的去减少哈希冲突，如上面举的例子就是将两个uint合成一个ull，保证每一个hash(S)是唯一的。数据量越大 unordered_map 的复杂度显然就越大，所以保险起见，可以尝试把 map 和 unordered_map 这两种写法都写出，用对拍比较快慢，然后选出快的交上去。
deque 与 list
deque 就是双端对列，顾名思义就是两端都能执行 push，pop和查询操作的队列。当然它不同于队列，它可以随机访问队列中的任何一个元素。
但这样的不知道好不好的东西，还是STL，自然会有很大的空间复杂度，它需要至少 16 倍的空间，不过你最好把它直接当成 100 倍空间，要慎用！更具体的可以去看 cppreference。在某年 NOIP 时，许多选手都因为开了 1e6 个 deque 直接炸掉了。由此也可见 dq 的不好用之处。那么有没有更好的东西？
通常我们不需要随机访问 dq 中的元素，此时我们就可以使用 list 也就是双向链表作为代替。list 使用的空间可以按 1 倍算，现在 dq 常用的函数，list 都有，具体也可以去看 cppreference。
总之，不要轻易的使用 dq。
set 与 multiset
首先在 警钟 中我们提到过：
如果set(或multiset)存的元素是一个结构体(Node)时，需要用operator<重定义这个符号，但是这个函数中需要比较Node中所有的元素。例如有两个值a和b，但是如果只比较(Node)x.a和a的值但是整个函数内没用用到b（即比较与b无关），那么set会将两个a相同的结构体当成同一个结构体处理，例如se.insert({2,0});se.insert({2,1});，那么此时se.size()==1，se中的最后一个元素的b==0;
set 是一个由红黑树实现的有序集合（不可重复），multiset 则可重复。因为其有序，我们可以使用它的成员函数 lower_bound 和 upper_bound 来进行二分查找元素（注意函数返回的是一个迭代器）。
insert 可以插入元素或节点，erase 可以删除元素。需要注意的是，在 multiset 中如果使用 erase 删除元素 $x$，那么容器中的所有 $x$ 都会被删除，你应该使用 st.erase(st.find(x)) 来删除一个 $x$。
用一下事例进行理解：
#include<bits/stdc++.h>
using namespace std;
int main(){
multiset<int>st={1,4,3,3,2};
for(auto s:st)cout<<s<<" ";
cout<<endl;
st.insert(4);
for(auto s:st)cout<<s<<" ";
cout<<endl;
cout<<st.count(4)<<endl;
st.erase(4);
for(auto s:st)cout<<s<<" ";
cout<<endl;
st.insert(4);
st.erase(st.find(3));
for(auto s:st)cout<<s<<" ";
cout<<endl;
return 0;
}
程序输出：
1 2 3 3 4
1 2 3 3 4 4
2
1 2 3 3
1 2 3 4
数据结构
PS:
线性数据结构
单调栈
顾名思义，单调栈即满足单调性的栈结构——OI-Wiki
单调栈的模板：P5788【模板】单调栈
是的单调栈有什么好看的，模板放一下差不多得了：
单调队列
顾名思义，单调队列的重点分为「单调」和「队列」。
「单调」指的是元素的「规律」——递增（或递减）。
「队列」指的是元素只能从队头和队尾进行操作。
——OI-Wiki
当然这里的队列指双端队列。
最常用的便是滑动窗口或者说区间最大值：P1886 滑动窗口 /【模板】单调队列
并查集
并查集，顾名思义，是支持合并与查询操作的集合
——沃兹基硕德
原理很简单，复杂度可以当成线性的（常数基本不超过 4），模板：P3367【模板】并查集
并查集简单的来说就是路径压缩，并查集还能再装一些“插件”：
扩展域： P1525[NOIP 2010 提高组] 关押罪犯，P2024[NOI2001] 食物链
伪删除：啊大概就是如果我想把一个点从并查集删除的话，不需要真的移除，只要把它对集合的贡献减去即可。暂时没有例题。
树形数据结构
树状数组
一张图简介：
这是一颗有 $n$ 个节点数树，它满足以下性质：
- 对于节点 $x$，它所代表的区间长度（即上图蓝色区间）为 lowbit(x)。
- 对于节点 $x$，它的子节点个数为 lowbit(x) 在二进制下的位数。
- 除树根外，节点 $x$ 的父节点为 x+lowbit(x)。
- 树的深度为 $\log(n)$
读者自证不难
（设 $x$ 在二进制下最低位的 $1$ 为第 $y$ 位，则 lowbit(x)=$2^i$，即 $x\&-x$）
以单点修改前缀和查询举例，对于节点 $x$，我们记 $c_x$ 为该节点所对应的区间中的和，那么查询函数如下：
int ask(int x){
int ans=0;
while(x)ans+=c[x],x-=x&-x;
return ans;
}
单点修改函数如下：
void add(int x,int d){
while(x<=n)c[x]+=d,x+=x&-x;
}
它可以写的非常简洁！
当然这只是最基本的用法，树状数组可维护的东西只需满足答案可合并与可拆解，因此你可以用它来维护区间修改单点查询，甚至区间修改区间查询。
这里放一段区间加区间和查询的代码（P3372【模板】线段树 1）
线段树
SegmentTreeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee~~~
众所周知线段树在考场上是用来骗分的！
一张图简介：
（你注意到图片能点了吗几百年前写的文章怎么这么【】）
线段树的功能取决于其 Merge 函数（懒修改函数随之而变），代码就浅浅的放一下吧：
复杂度证明是个很有趣的东西，可惜我不会。
线段树的变种也有很多，可惜我也不会。
huhuhuhuhuhuhuhuhuhuhuhuhuhuh
图论
拓扑排序
一个我自己猜想的结论
拓扑排序时我们反向建边，然后最后得到的拓扑序反着输出，依旧能通过SPJ。至少这个结论在 这题 里是能AC的。以及这是我的证明，不知道是否严禁：
如何建反：将本应从 u 指向 v 的边连成从 v 指向 u 的边。
那么原本应该在v之前都走的点（只有这些点都走过才能走v），我反过来的做法会让这些点都在v之后走（也就是只有v走过才可能走这些点），最后得到的顺序整体翻过来，就是那些点都在v之前走完了。
数学&数论
树学和树论说完了我们就来说数学和数论。
gcd/lcm
俗称辗转相减法，属于常识，当然你不需要背模板，C++有求gcd的函数：__gcd。只要记得在求 gcd 之前判断会不会出现负数的情况（CSP-J2023 T3令我印象深刻）。记住复杂度为 $O(\log(a+b))$ 即可。但还是放下模板吧：
function<int(int,int)>gcd=[&](int a,int b){return b?gcd(b,a%b):a;};
就一行(
质数
线性筛
埃氏筛大概是：任意整数 $x$ 的倍数都不是质数，因此从小到大遍历每一个 $x$，如果还未被标记则 $x$ 是质数，然后去标记大于等于 $x^2$ 的 $x$ 的所有倍数。复杂度为 $O(n \log \log n)$。
显然埃氏筛还是会重复标记合数，“根本原因是没有确定出唯一的产生 $x$ 的方法”。线性筛则是保证了只有 $x$ 的最小的质因数才会标记 $x$，详细的算法原理可以去 OI Wiki。代码是这样的：
vi prm,v(N+1);
for(int i=2;i<=N;i++){
if(v[i]==0)v[i]=i,prm.emplace_back(i);
for(auto p:prm){
if(p*i>N||v[i]<p)break;
v[i*p]=p;
}
}
建议理解原理后即可背下。
欧拉函数
定义：$\varphi (n)$ 为 $1\sim n$ 中与 $n$ 互质的数个个数。
若 $n=\prod \limits_{i=1}^{m}p_i^{c_i}$ 则 $\varphi (n)=n\times \prod \limits_{i=1}^{m}(1-\frac{1}{p_i})$，使用 $n$ 减去与 $n$ 不互质的数并化简即可推出。
显然计算 $\varphi (n)$ 只需对 $n$ 分解质因数即可：
int phi=n;
for(int i=2;i*i<=n;i++){
if(n%i!=0)continue;
phi=phi/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)phi=phi/n*(n-1);
性质：
- $1\sim n$ 中与 $n$ 互质的数的和为 $\frac{n\times\varphi (n)}{2}$（与 $n$ 互质的数总是成对出现）
- 欧拉函数是积性函数，即若 $a,b$ 互质，则 $\varphi (ab)=\varphi(a)\varphi(b)$。
- $\sum \limits_{d|n} \varphi(d)=n$
线性求欧拉函数
在线性筛的基础上计算欧拉函数：
vi prm,v(N+1),phi(N+1);
phi[1]=1;
for(int i=2;i<=N;i++){
if(v[i]==0)v[i]=i,prm.emplace_back(i),phi[i]=i-1;
for(auto p:prm){
if(p*i>N||v[i]<p)break;
v[i*p]=p;
phi[i*p]=phi[i]*(p-(p<v[i]));//为了防止避免浮点运算所以对原式做些变化
}
}
拓展欧几里得
也就是俗称的 exgcd：$ax+by=\gcd(a,b)$。
那么如何求解呢？既然名字里都有 gcd 了，显然与 gcd 有关。我们只考虑 $\gcd(a,b)=1$ 的情况，如果不为 1 只需讲方程两边同时除去 $\gcd(a,b)$ 即可。
用 gcd 的方法，我们将原方程变为 $bx’+(a%b)y’=1$，这样一直操作到最后能得到 $ax^{若干’}+by^{若干’}=1$，其中 a=1（即 $\gcd(a,b)$）b=0。显然有的一组解为 $x^{若干’}=1,y^{若干’}=0$。
那么求出 $bx’+(a%b)y’=1$ 的解与原方程的解的关系就可以求出原方程的解了（废话吧）：
$$
\begin{array}{l}
bx’+(a\%b)y’\\
=bx’+(a-b\left\lfloor\frac{a}{b}\right\rfloor)y’\\
=bx’+ay’-b\left\lfloor\frac{a}{b}\right\rfloor y’\\
=ay’+b(x’-\left\lfloor\frac{a}{b}\right\rfloor y’)\\
\therefore ax+by=1的解为\begin{cases}x=y’\\y=x’-\left\lfloor\frac{a}{b}\right\rfloor y’\end{cases}
\end{array}
$$
显然 exgcd 函数也能帮助我们求 $\gcd(a,b)$，所以我们一般会将 x,y 作为可被修改的参数传入函数，而函数的返回值则是 $\gcd(a,b)$。代码：
function<int(int,int,ll&,ll&)>exgcd=[&](int a,int b,ll& x,ll& y){
if(b==0){x=1,y=0;return a;}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;//为了少写点(毕竟是模板)所以做一些变化
return d;
};
exgcd 可用于求同余方程 $ax\equiv n\pmod b $ 的解。
逆元
定义：$a^{-1}$ 为 $a$ 的逆元。
有什么用呢？在模运算意义下，+,-,*,^ 都是可以直接算的，但除法就不行。但除以一个数等于乘以它的逆元，因此我们求出一个数的逆元就能将除法转换成乘法了。那么如何求解？
F1:
显然 $a\times a^{-1}\equiv 1\pmod m$，这是什么，这是 exgcd！用 exgcd 就可以求了（前提为 $\gcd(a,m)=1$ 才能求）。
F2:
同余中有一条定理为若 $a,m$ 互质则 $a^{b}\equiv a^{b \mod \varphi(m)}\pmod m$。那么如果 $a,m$ 互质，$a^{-1}\equiv a^{-1 \mod \varphi(m)}\pmod m$，有什么用呢？你可以将 $\varphi(m)$ 求出，不过大多数情况下模数应该是个质数，那么 $\varphi(m)$ 就等于 $m-1$，即 $a^{-1}\equiv a^{m-2}\pmod m$，这又是什么，这是快速幂！
线性求逆元
顾名思义，我们需要通过线性的复杂度求出 $1\sim n$ 中所有数的逆元。求单个逆元的复杂度是 $\log$ 的，但整体求显然我们可以做出一些优化，例如之前线性求欧拉函数就可以通过递推求解。
F1
如果你只需要求 $1\sim n$ 的所有逆元，可以用一下方法推导：
$$
\begin{array}{l}
假设我们已经求出 1\sim i-1 的所有逆元\\
现在要求方程 i^{-1}\equiv x\pmod p 的解\\
设 p=k\times i+r(其中0\le r\lt i) 则\\
k\times i+r\equiv p\equiv 0\pmod p\\
k\times i\equiv -r\pmod p\\
-k\equiv r\times i^{-1}\pmod p\\
i^{-1}\equiv -\frac{k}{r}\pmod p\\
这里能直接除r是因为r\le i-1,它的逆元是已知的\\
i^{-1}\equiv -p/i\times (p\%i)^{-1}\\
\therefore i^{-1}=(p-p/i)\times (p\%i)^{-1}\% p
\end{array}
$$
我们便可写出一下代码：
vi inv(n+1);//inv[i]表示i的逆元
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=ll(p-p/i)*inv[p%i]%p;//注意longlong!
}
F2
不过呢，一般需要 $1\sim n$ 的逆元的话，大概就是组合计数了，那么此时我们还需要 $1!\sim n!$ 的逆元，就需要换种方法递推了。
我们用 fct[i] 表示 $i!$，用 inv[i] 表示 $i$ 的逆元，用 invfct[i] 表示 $i!$ 的逆元，便可得到以下代码：
vi fct(n+1),inv(n+1),invfct(n+1);
fct[0]=1;
for(int i=1;i<=n;i++){//递推求 1!~n! (mod p)
fct[i]=(ll)fct[i-1]*i%p;
}
invfct[n]=ksm(fct[n],p-2);//使用快速幂求逆元(前提题目保证p为质数)，快速幂函数就省略不写了
for(int i=n;i>=1;i--){//注意是倒着推
inv[i]=(ll)fct[i-1]*invfct[i]%p;// i^-1=1/i=(i-1)!/i!=fct[i-1]*invfct[i]
invfct[i-1]=(ll)i*invfct[i]%p;// 1/(i-1)!=i/i!=i*invfct[i]
}
组合计数中通常情况下不会用到 inv 数组，可适当省略。
数论分块
举个栗子，令 $f(x)$ 为 $x$ 的约数个数，求 $\sum\limits_{i=1}^{n} f(i)$。
如果你直接将每个 $f(i)$ 都求出的话，复杂度是 $O(n\sqrt n)$ 的，智慧的 OIer 们是不能接受的，因此我们要换个角度来想：$1\sim n$ 中有 $i$ 这个因数的数的个数，是 $\left\lfloor\frac{n}{i}\right\rfloor$ 个。
$\sum\limits_{i=1}^{n} \left\lfloor\frac{n}{i}\right\rfloor$ 直接求就是 $O(n)$ 的，不过这是经典的整数分块。你可以随便取一个 $n$，最好是质数，例如 37，然后列出所有的 $\left\lfloor\frac{n}{i}\right\rfloor$，你会发现每种 $\left\lfloor\frac{n}{i}\right\rfloor$ 是连续出现的（区间），且一共有 $\sqrt n$ 种。那么现在我们知道一个区间的左端点 $l$，它的右端点就是 $\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$，套娃(
int sum=0;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
sum+=(r-l+1)*(n/l);
}
那么现在，我们成功将 $O(n\sqrt n)$ 优化成了 $O(\sqrt n)$，为什么会减少这么多？首先看最暴力的 $O(n\sqrt n)$ 的做法，在求每个 $f(i)$ 时，我们需要扫描所有小于等于 $\sqrt i$ 的数然后去统计约数个数，但这 $\sqrt i$ 个数中并不是所有的数都对答案有贡献，所以这个方法浪费了很多时间。将其转化成 $\sum\limits_{i=1}^{n} \left\lfloor\frac{n}{i}\right\rfloor$ 后，通过列表我们又发现不同的 $i$ 求出的 $\frac{n}{i}$ 是有重复的数的，且是有规律的。顺着规律化简就又去掉了许多重复的计算，最终得到了 $O(\sqrt n)$ 的复杂度。
这就是数学题常见的优化思想。
组合计数
省流：哦不！
加法原理，乘法原理，$A_n^m$，$C_n^m=\frac{n!}{m!(n-m)!}$ 这几个基本的定义就不说了，不过要注意 $C_n^m$ 这种写法只是小奥中的一种【】的写法，它通常被写作 $\binom{n}{m}$，主要说的是 $C_n^m$ 的性质：
- $C_n^m=C_n^{n-m}$
- $\sum\limits_{k=0}^{n} C_n^k=2^n$
- $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
根据定义它们都是显然的，最后一条被用作递推求 $C_i^j$，但这是 $O(n^2)$ 复杂度的，太慢了。我们应该直接根据它的定义去算，上文已经讲过如何递推求 $1\sim n$ 的阶乘的逆元，这里直接用就可以了。
模数不是质数
在逆元中我们提到了几种常数或线性求逆元的方式，但这些方式都有一个前提：$a$ 与 模数 $m$ 互质时 $a$ 才有逆元。在模 $m$ 意义下如果 $a$ 不与 $m$ 互质，我们就没办法做除法运算。
所以 $m$ 不是质数时我们就没办法求组合计数了吗？还是有办法的。
首先我们知道 $\binom{n}{m}$ 一定是个整数，毕竟 $n$ 个球里选出 $m$ 个的方案数不可能为小数（感性理解即可）。因此对于组合数的定义 $\binom{n}{m}=\frac{\prod\limits_{i=n}^{n-m+1}i}{\prod\limits_{i=m}^{1}i}$ 中，$\prod\limits_{i=n}^{n-m+1}i$ 一定是 $\prod\limits_{i=m}^{1}i$ 的倍数。
因此我们可以将分子和分母进行质因数分解，对于每一个质因子，用分子的系数减去分母的系数就是答案中的系数。这样我们就避免了除法运算。
用到此方法的题目：P3200[HNOI2009] 有趣的数列（真有趣）
二项式定理
$(a+b)^n=\sum\limits_{k=0}^{n}\binom{n}{k} a^k b^{n-k}$
将 $(a+b)^n$ 全部展开后，$a^k b^{n-k}$ 的系数就是 $C_n^k$（选 $k$ 个 $a$，剩下的是 $n-k$ 个 $b$），很显然。
Catalan 数
也就是卡特兰数，其最经典的定义是“0 和 1 各有 $n$ 个，将它们排序得到一个长度为 $2n$ 的序列且满足任意前缀中 0 的个数不少于 1 的个数的序列的数量”，而其最经典的用法就是这题：P1044[NOIP 2003 普及组] 栈。
对于卡特兰数的求解，常见的公式有以下几种：
- $C_i=\left\{\begin{matrix}
\sum\limits_{i=1}^{n}C_{i-1}C_{n-i} & n\ge 2,n\in N_+\\
1 & i=0,1
\end{matrix}\right.$ - $C_i=\binom{2i}{i}-\binom{2i}{i-1}=\frac{\binom{2i}{i}}{i+1}=\frac{\prod\limits_{j=i+2}^{2i}j}{\prod\limits_{j=1}^{i}j}$
- $C_i=C_{i-1}\frac{4i-2}{i+1}$
【1的证明过程】
至于 3 应该是可以通过 1 来证的，所以我懒得写了。
多重集(可重集)
多重集 $S=\{n_1\cdot a_1,n_2\cdot a_2,\dots ,n_k\cdot a_k\}$ 表示 $S$ 由 $n_i$ 个 $a_i(1\le i\le k)$ 组成的。令 $n=\sum\limits_{i=1}{k} n_i$，则 $S$ 的全排列（考虑顺序）个数为：
$$
\begin{array}{l}
\binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3}\dots\binom{n_k}{n_k}\\
=\frac{n!}{n_1!(n-n_1)!}\frac{(n-n1)!}{n2!(n-n_2)!}\dots \frac{n_k!}{n_k!} \\
=\frac{n!}{\prod_{i=1}^{k}n_i}
\end{array}
$$
如何求从 $S$ 中取出 $r(r\le n_i)$ 个数的组合数（不考虑顺序）个数？原问题等价于求 $x_1+x_2+\dots x_k=r$($x_i$ 为自然数)的解的数量，这是我们小奥里面的的插板法。最后可以得到答案为 $\binom{k+r-1}{k-1}$。【对于 $r$ 更一般的情况则需要用到容斥原理】
min/max
首先 $\min$ 和 $\max$ 最基本的转换是 $\min(x,y)=x+y-\max(x,y),\max(x,y)=x+y-\min(x,y)$。
它们各自单独的转换是 $\min(x,y)=\frac{x+y-|x-y|}{2},\max(x,y)=\frac{x+y+|x-y|}{2}$。
转换：像 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\min(|a_i-a_j|,|b_i-b_j|)$ 这样的式子，显然 $\min$ 无法直接拆开，尝试递推等思想后依旧无法解决，那么我们只能看看 $\min$ 本身如何转换了。
如果直接转换得到 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac{|a_i-a_j|+|b_i-b_j|-||a_i-a_j|-|b_i-b_j||}{2}$，还是【】
切比雪夫距离
定义：$(x1,y1)$ 与 $(x2,y2)$ 的切比雪夫距离为 $\max(|x1-x2|,|y1-y2|)$，即 $(x1,y1)$ 走到 $(x2,y2)$（$(x1,y1)$ 在 $(x2,y2)$ 的左下方），每步只能向上，向右，向右上走，最少几步能走到。
【】
语法
三目运算
语法为 条件?如果为真返回值:如果为假返回值，拿 gcd 举例 return b?gcd(b,a%b):a 和 if(b==0)return a;else return gcd(b,a%b); 是一样的效果，更加的简短豪康了。
至于运算优先级的问题，保险起见你最多在整条语句外面加个括号，是为了防止语句内的其他运算跟外面的运算出问题，?: 这个运算本身不会出什么问题，它不可能再被解释成其他的语句了。
Lambda表达式
简单地说，就是能把一切东西都往 main 函数里塞的工具。
常用的形式大概是这样的：
auto f=[&](int a,int b){
//↑auto 能自动根据你的返回值推断出表达式的类型,这里实际的类型为function<string(int,int)>
// ↑ &表示函数中可以使用或修改外部变量，不写&则表示不能使用或修改外部变量
// ↑跟普通函数一样，这里是调用f时需传的参数
//函数内容
return str;//返回值为string
};//注意这只是个表达式，一条语句，f从某种角度来说还是个被定义的变量，这里需要分号！
但是当你想让函数自己调用自己的时候 auto 就不智能了，你需要手动写上 f 的类型，否则【】的 C++ 无法知道表达式的类型，拿最简单的计算 $\sum \limits_{i=1}^{n} i$ 举例：
function<long long/*函数返回值类型*/(int/*所有传进来的参数的类型*/)>f=[&](int n){
if(n==1)return 1;
return f(n-1)+n;
};//分号！
【未完工】
cout保留精度
因为在使用了 cin.tie(0)->sync_with_stdio(0); 后便无法使用 printf("%.2f",x); 去保留精度。因此我们需要使用 cout<<fixed<<setprecision(2)<<x; 来达到同样的效果。
一些函数
似乎都是 STL里的东西？
fill
fill(v.begin(),v.end(),1e9);将v.begin()到v.end()指向的元素赋值为 1e9，复杂度线性。
reverse
reverse(v.begin(),v.end());翻转v中的元素，复杂度线性。（这玩意儿甚至在 23 年 J 组初赛时考到了）
memcpy
memcpy(a,b,sizeof b);将 $b$ 数组赋值到 $a$ 数组（$a,b$ 数组长度相同）。
next_permutation
next_permutation(v.begin(),v.end());将 $v$ 变为 $v$ 的下一个排序，通常用于求出 $1\sim n$ 的全排列。
功能类似 sort，只不过是以归并排序（稳定排序）的方式实现的
优化与卡常
注意此处的优化只是语法层面的优化，与算法无关。
卡常
max&min
C++11 有个新语法，就是 max 可以用来比较多个数的值：
max({a[1],a[2],a[3]...a[n]})
正常情况下，如果你不开 O2，那么这种方法比 max(a[1],max(a[2],...)) 这种比较方法要慢一倍。但是比赛的时候基本上都是默认开 O2 的，新的语法比旧的语法要快一些。
inline
应该是很古老的东西了，在定义的函数前面加上这个能玄学的加快一点速度。不过现在的机子都没有那么差了，加上了几本跟没加是一样的。
stable_sort
功能与sort没有区别，只不过是用归并排序（稳定排序）对数组进行排序，也许会快点？不过都要排序数组了一般也不能卡你 $O(n\log n)$ 的程序。
clock骗分
int st=clock();//单位为ms
...
if(clock()-st>=999){
...
exit(0);
}如果你的程序会 TLE，并且这么久还没找到解，我们可以大胆的猜测它没有解，这时我们就加上他，当运行时间快到限制时，认定这组数据是无解的，然后结束程序。
需要注意的是，clock() 函数也会浪费一点时间的，慎用。
多维数组优化
如果我们现在需要一个大小为 2e5 * 64 的二维整形数组 $a$，为了程序更高的效率，我们应将它写作：
int a[64][200005];
而不是 int a[200005][64];。（也就是尽量将范围小的维度开在前面）
这两种写法在数据范围大的情况下可能能有一倍的差距。
二进制
位运算
位运算的特点就是在二进制表示下不会进位，每一位与其他位计算出的值都无关。一些题目下我们便可将数据的值（32 位或 64 位整型）的每一位分别处理。
bitset
bitset 也算是一种数据结构，他能被当做二进制数使用，两个 bitset 之间可以正常的进行按位异或、与、或运算。但是他不止能够存 64 位，类似 bool 数组，你可以将它的大小开到 1e6 都行。两个 bitset 做位运算的时间复杂度为 $O(bitset大小/计算机位数)$，通常来讲计算机位数是 $64$ 位的。
bitset 也常被用作路径压缩（如 dp 时）或集合计算。
当我们想求图上两节点的公共祖先之类的问题时，在 $n^2\le 6\times 10^9$ 的情况下可以考虑使用 bitset 记录每个点是不是一个点的祖先。求祖先交集，将两个节点的 bitset 进行与(&)运算即可。同理，将两个 bitset 进行或(|)运算即可得到并集。
__builtin_
__builtin_clz(x)用于求 $x$ 的二进制数中最高位的1前面有多少个0，常见的用法是用于求 log2(x)=31-__builtin_clz(x)($x$ 为int)或log2(x)=63-__builtin_clzll(x)($x$ 为 longlong)。
__builtin_ctz(x)用于求 $x$ 的二进制数中最低位的1后面有多少个0，__builtin_popcount(x)用于求 $x$ 二进制数中1的个数，需要注意这个函数的参可以传 long long 但是最大只会返回 32（也就相当于求二进制下前 32 位中有多少个 1，不如自己手写一个）。
以上函数基本上就是 $O(1)$ 的，可以放心食用。
OUR TEAM, HAVING A 32,768 THREADS AND A 32th GEN INTEL CORE i16-21,247,483,647H CPU WITH
9,223,372,036,854,775,808GB OF MEMORY TO BLOW YOUR SERVER UP!!!! IF YOU DON’T WRITE BACK AN EMAIL PROMISING U.S.1,145,141,919,810$, BEFORE 12:AM (UTC-4), JUNE 7, 2025, WE WILL IMMEDIATELY DDOS YOU WITH OUR CLIENT VIA 16 VPNS.