数据结构

单调栈

单调栈是一种通过维护单调性用 $O(n)$ 的时间求解前面的数据对后面的数据没有影响的问题。

顾名思义，单调栈其实就是一个栈，手写和 STL 都可以。
写单调栈，首先要确定这个栈是要单调递增还是单调递减。

一个单调栈的模板题：求一个长度为 $n$ 的序列中每一个数的左边第一个比它小的数，如果没有，则输出 $0$。其中 $n\le 10^6$。
发现这个题目如果每一次暴力去查找的话，时间复杂度是 $O(n^2)$，显然不可以通过。
这个时候就要维护一个单调递增栈，每一次要放入数据时，就判断栈顶是否比该元素大，如果是，则一直弹栈，直到栈顶比该元素小。而此时的栈顶就一定是左边第一个比该元素大的数。最后把该元素入栈即可。
时间复杂度和空间复杂度都是 $O(n)$。

注意点
1.注意开始遍历数组之前，要往栈里放一个 $0$。
2.记得在判断栈顶单调性并弹栈时判断栈里面有数。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int a[N];
int s[N],top;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	s[++top]=0;
	for(int i=1;i<=n;i++){
		while(top&&a[i]<=s[top])top--;
		cout<<s[top]<<' ';
		s[++top]=a[i];
	}
	return 0;
} 

单调队列

单调队列是一个类似于单调栈的知识点，都是通过维护单调性用 $O(n)$ 的时间求解前面的数据对后面的数据没有影响的问题。

和单调栈差不多，但是单调队列使用的是栈而不是队列。其中使用队头来维护数据，队尾来维护单调性。

对于P1886 【模板】单调队列 / 滑动窗口，可以使用单调队列维护下标，因为用值不可以知道下标，但用下标可以知道值。

具体操作如下：
当队列非空时，且窗口是大于理想大小，就

head++

a[i]

tail--

注意点
1.要特判大小大于等于窗口大小，也就是

i>=k

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int n,k;
int q[N];
int head=1,tail;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(head<=tail&&i-q[head]+1>k)head++;
		while(head<=tail&&a[q[tail]]>=a[i])tail--;
		q[++tail]=i;
		if(i>=k)cout<<a[q[head]]<<' ';
	}
	cout<<'\n';
	head=1,tail=0;
	for(int i=1;i<=n;i++){
		while(head<=tail&&i-q[head]+1>k)head++;
		while(head<=tail&&a[q[tail]]<=a[i])tail--;
		q[++tail]=i;
		if(i>=k)cout<<a[q[head]]<<' ';
	}
	return 0;
}

并查集

并查集是一种非常高效的树形数据结构，其可以在接近 $O(1)$ 的时间复杂度来做到合并，查询一些关于一些数据之间的关系的问题。

以下内容中，$fa_x$表示节点 $x$ 的父节点。
以板题为例，其实就是有 $n$ 个节点，操作就是让你把这些的所在的集合合并或者查询是否在一个集合中。
我们可以把每一个节点在刚开始的时候定义为一个独立的点，且为一个集合的根，即 $fa_x=x$。

初始化搞定了，考虑查询节点 $x$ 的根怎么实现。
发现，当 $fa_x=x$ 时，节点 $x$ 为根。所以直接从一个节点往父亲跳，当当前阶段满足根节点的条件时，就返回当前节点。
但是，这样做的时间复杂度最慢是 $O(n)$，考虑优化。
这里要用到一个叫路径压缩的技巧，顾名思义，就是在查找的过程中将这个树里的路径压缩，发现当一个节点的根也同样是他父节点的根，所以在查询时，把查询的结果也放在 $fa_x$ 中，也就是 $fa_x=find(x)$。

合并操作在查询操作写完之后就很好写了，只用将 $x$ 的根的父节点连到 $y$ 的根上，也就是将以 $x$ 的根为根的一整棵树拼到以 $y$ 的根为根的树上，成为它的一个子树。即 $fa_{find(x)}=find(y)$。

总得时间复杂度为 $O(m\alpha(n))$，其中 $\alpha(n)$ 在对于 $n\le 10^{2^{10^{19279}}}$ 时，$\alpha(n)\le 5$。所以完全可以看作一个常数给省略掉。

并查集还可以放扩展域，即 $1$ 到 $n$ 放一组数据，$n+1$ 到 $2n$ 一组数据。

注意点 在进行合并操作时，切记是使用两个节点的根来合并的，而不是用两个点。
扩展域并查集要开双倍空间。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fa[N];
int n,m;
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
bool same(int x,int y){
	if(find(x)==find(y))return true;
	else return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1)merge(x,y);
		else {
			bool f=same(x,y);
			if(f)cout<<"Y\n";
			else cout<<"N\n";
		}
	}
	return 0;
} 

01Trie

01Trie 是一种基于 Trie字典树 上的数据结构，是一种解决关于异或类问题的数据结构。

01Trie 的本质就是把每个数变成二进制串再放到字典树上，在贪心求解。

把每一个数转化成 $31$ 位二进制，想让它的异或值最大，那就是让 $0$ 尽量遇到 $1$，$1$ 尽量遇到 $0$。所以就要从最高位开始，尽可能的让这个数的在二进制下的每一位都与枚举的数不同，如果不能满足，那就相同。
实现就是把每一个数的二进制放在 Trie 上维护，让后直接上模板即可。

貌似有更高端的压位01Trie。学了再补。

时间复杂度 $O(nk)$，$k$ 是个 $\le100$ 的常数。

注意点 1.要从高位到低位枚举，且枚举 $31$ 位二进制时注意是到 $i\ge 0$ 而不是 $i\ge 1$。
2.$son$ 数组的第二位因为是存二进制，所以只用开 $5$ 就够了。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int son[N][5];
int cnt[N],idx;
void insert(int x){
	int p=0;
	for(int i=31;i>=0;i--){	
		int u=(x>>i)&1;
		if(!son[p][u])son[p][u]=++idx;
		p=son[p][u];
	}
	cnt[p]++;
}
int query(int x){
	int p=0;
	int res=0;
	for(int i=31;i>=0;i--){
		int u=(x>>i)&1;
		if(son[p][1^u])res=res^(1<<i),p=son[p][1^u];
		else p=son[p][u];
	}
	return res;
}
int n,a[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]);
	}
	int mx=-1e9;
	for(int i=1;i<=n;i++)mx=max(mx,query(a[i]));
	cout<<mx;
	return 0;
}

字符串

字符串hash

字符串hash是一种高效查询类似子串判重的问题的东西。

当每次我们想比较两个字符串子串是否相同时，一般情况下，要暴力匹配，时间复杂度最坏 $O(n)$。

这时，字符串hash就有作用了。
字符串hash的原理就是给每一个串赋予一个哈希值，同过比较哈希值，就可以实现 $O(1)$ 对比。
现在的问题就是：怎么实现这个哈希值？

设有一个进制 $B$，则一个字符串 $s$ 的哈希值为：

其实就是一个 $B$ 进制的位权展开。
$B$ 通常取 $131$ 或 $13331$。

但这时有一个问题：按这样计算，不是很容易溢出吗？

确实是，通常来说，我们为了避免溢出，会使用取模。
但在字符串哈希中，根据前人经验取模的时间慢和哈希冲突的分析，我们不是用取模来，而是将 hash 的值设置为

unsigned long long

现在这一个 $\text{hash}$ 数组的求法已经推出来了，预处理的时间复杂度是 $O(n)$，所以我们查询区间 hash 需要使用 $O(1)$ 的复杂度。

设区间左为 $l$，右为 $r$，$h_i$ 表示从 $1$ 到 $i$ 的串的哈希值，则 $l$ 到 $r$ 的串的哈希值为：

这个式子是如何推出来的呢？

用类似前缀和的思想，使用 $10$ 进制类比一下。有一个串 $12345$，则 $h$ 数组为 ${1,12,123,1234,12345}$，如果我们要求 $2$ 到 $4$ 之间的哈希值，手推一下，发现是 $234=1234-1\times 1000$。再举个例子，求 $3$ 到 $4$，发现答案是 $34=1234-12\times 100$。
推出来是右端点减去左端点，但是左端点要乘上两个点相差的距离来补全。

还有一些技巧，就是使用多个哈希，比如双哈希和三哈希以加快查询效率和减少冲突。
比如双哈希时就是都要比较。

注意点
1.计算 $B$ 的任意次方要使用 $O(n)$ 的预处理和 $O(1)$ 查询，如果用快速幂的 $O(\log n)$ 的话总复杂度是 $O(n\log n)$。
2.使用多哈希的时要注意，每一个哈希的 $B$ 值要不一样，且一定要是质数。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B=13331;
const int N=1e6+10;
char s[N];
ull h[N];
ull p[N];
int n;
void get(){
	p[0]=1;
	for(int i=1;i<=n;i++){
		p[i]=p[i-1]*B;	
	}
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]*B+(s[i]-'a'+1);
	}
}
bool ask(int l1,int r1,int l2,int r2){
	ull a=h[r1]-h[l1-1]*p[r1-l1+1];
	ull b=h[r2]-h[l2-1]*p[r2-l2+1];
	//cout<<"ask:"<<a<<' '<<b<<'\n';
	return a==b;
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	get();
	int m;
	cin>>m;
	while(m--){
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		if(ask(l1,r1,l2,r2)){
			cout<<"Yes\n";
		}
		else cout<<"No\n";
	}
	return 0;
}

KMP

KMP 算法是解决一个串在另一个串中的匹配问题的算法。

如果给定两个串，让你求第二个在第一个中出现的位置。设第一个串是 $s$，第二个是 $t$，长度分别是 $n$ 和 $m$。

首先可以想到暴力匹配，直接扫过去，如果不匹配就跳过，理想时间复杂度是 $O(n)$，但是如果构造一个每一位都匹配的数据，就会被卡成 $O(nm)$。

发现暴力中，失配了就直接跳到开头，这样前面的查找就归零了，效率底下。

KMP 就是可暴力差不多，但是每一次失配不是跳会开头，而是跳会某个数组。核心思路是：主串指针 $i$ 不回退，只通过调整模式串指针 $j$ 来“滑动”模式串。

现在的问题是：要跳多远？

发现要让模式串向右滑动后，能够再次与主串对齐，我们需要满足一个条件：滑动后，模式串“新头部”的内容，必须与主串“刚匹配过”的内容一致。 也就是主串“刚匹配过”的内容等于模式串“已匹配”的后缀。
所以问题转化为：模式串的“前缀”必须等于模式串的“后缀”。

定义 $next_j$ 是当模式串在下标 $j$ 处发生失配时，新的 $j$ 应该移动到的位置。
其实就是$next_j =t_0…t_j−1$ 这个子串LCPS(最长公共前后缀长度)。

构造 $next$ 的过程，就是 $t$ 与自己匹配的过程。
注意构造是也用到了 KMP 失配时回溯的思想。

先构造 $t$ 的 $next$ 数组，然后直接匹配 $s$ 和 $t$。
时间复杂度 $O(n+m)$，空间复杂度 $O(n)$。 注意点 注意 $i$ 和 $j$ 的初始值，和构造 $next$ 数组时是到 $n$，匹配时是到 $m$。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N],t[N];
int ne[N];
int main(){
	scanf("%s%s",s+1,t+1);
	int n=strlen(t+1),m=strlen(s+1);
	for(int i=2,j=0;i<=n;i++){
		if(j&&t[i]!=t[j+1])j=ne[j];
		if(t[i]==t[j+1])j++;
		ne[i]=j;
	}
	for(int i=1,j=0;i<=m;i++){
		if(j&&s[i]!=t[j+1])j=ne[j];
		if(s[i]==t[j+1])j++;
		if(j==n){
			cout<<i+1-n<<' ';
			j=ne[j];
		}
	}
	return 0;
}

字典树Trie

字典树是我感觉为数不多的懂算法比写代码简单的东西了。

字典树是解决多组字符串匹配的问题的数据结构。

过程类似查字典，是先找每个单词的首字母，在找第二个，以此类推。

在建树的过程中，每一个单词，先遍历这个单词，把这个单词放到树上，就是一个如果它的首字母有，就向下看有没有第二个，以此类推，如果有，就新建节点。
值得注意的是，在建树的过程中，每一个单词的结尾都要打上标记，这样才可以统计。

建完树之后，就是查找部分。

查找就是顺着这个树向下爬，如果不匹配，就直接返回，匹配就继续向下爬。
最后返回最后的节点的标记数。

定义 $son_{p,u}$ 代表第 $p$ 个节点的 $u$ 个儿子是谁。$cnt_p$ 表示以节点 $p$ 结尾的单词有多少个。$idx$ 表示节点数量。

刚开始先定义一个 $p$ 表示当前位置的指针。
遍历字符串，将当前字符 $c$ 映射成一个整数 $u$，可以得出 $son_{p,u}$ 是节点 $p$ 对于 $u$ 的路。
如果 $son_{p,u}$ 是没有值得，那么说明是没有这个点的，那么将节点数 $idx$ 加 $1$，让后给 $son_{p,u}$ 标记编号 $idx$。
标完节点之后，让 $p$ 跳到下一个节点 $son_{p,u}$ 就行了。
在遍历完单词之后，$p$ 跳到了最后一个节点，所以给 $p$ 这个节点标记，也就是 $cnt_p$ 加 $1$。

查询和建树基本一样，只是在 $son_{p,u}$ 没有值的时候直接返回 $0$，因为单词前缀断了就不可能匹配。
最后返回 $cnt_p$，也就是记录的次数。

字典树可以通过修改 $cnt$ 数组的含义来实现其他功能。

时间复杂度 $O(len)$，即字符串长度，空间复杂度好像是 $O(n|\Sigma|)$，其中 $n$ 为节点个数，$|\Sigma|$ 是字符集大小。
貌似使用哈希表可以做到 $O(n)$ 空间。

注意点
1.$son$ 数组的第一维要开 $\sum len$，也就是所以字符串的长度之和。
2.多测时清空 $son$ 数组和 $cnt$ 要手动清空，只用清空前 $idx$ 个就可以了。
3.注意题目中的字符映射，不一定只是小写字母。因此，也要注意 $son$ 数组的第二维开多大。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int cnt[N];
int son[N][30];
int idx;
int n,m;
char s[N];
void insert(char c[]){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!son[p][x])son[p][x]=++idx;
		p=son[p][x];
	}
	cnt[p]++;
}
int query(char c[]){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!son[p][x])return 0;
		p=son[p][x];
	}
	return cnt[p];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		insert(s);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%s",s);
		cout<<query(s)<<'\n';
	}
	return 0;
}

AC自动机

AC自动机是一种基于 Trie树 与 KMP 的解决多模式串匹配问题的算法。其实本质上是在 Trie 上跑 KMP。

先把每个每个模式串建到字典树上，然后手动去模拟一下匹配的过程。发现，当匹配一个串时，如果匹配失败，就做一个类似 KMP 要跳到另一个地方重新匹配，我们要求解的就是要跳到哪里。

定义 $fail_i$ 表示 $i$ 这个点失配后应该跳到的点的编号，$T_i$ 表示 Trie 上编号为 $i$ 的节点，$fa_x$ 表示节点 $x$ 的父亲。则如果 $i$ 的父节点 $fa_i$ 的 $fail$，也就是 $fail_{fa_i}$，满足 $fail_{fa_i}$ 这个点的子节点中有 $i$ 这个节点的字符，那么 $fail_i$ 指向这个子节点，也就是 $fail_i=x$ 满足 $T_x=T_i$ 且 $fa_x=fail_{fa_i}$；否则 $fail_i$ 指向根节点，也就是 $fail_i=0$。
求 $fail$ 的过程，可以用 bfs 按字典树的层序遍历。
定义 $ch_{p,u}$ 代表第 $p$ 个节点的 $u$ 个儿子是谁。
先把第一层的节点入队，也就是遍历 $26$ 个字母，满足 $ch_{0,i}$ 是有节点的，把它入队。
然后跑正常广搜，把队头 $p$ 取出来，每一个节点，遍历 $26$ 个字母，如果 $ch{p,i}$ 是有节点的，那么根据定义，得出 $fail_{ch_{p,i}}=ch_{fail_p,i}$，也就是以 $p$ 为父节点，满足有这个字符就更新 $fail$，把当前阶段 $ch_{p,i}$ 的 $fail$ 更新为父节点 $p$ 的 $fail$ 到 $i$ 的字符；如果没有这个节点，就进行一个记忆化的操作，让 $ch_{p,i}=ch_{fail_p,i}$ 把这个点连上。

把每个点的 $fail$ 处理出来之后，就是查询部分了。

查询的方法很简单，就是跑文本串，每个节点往下跑，匹配就走，没匹配就跳 $fail$，最后统计有多少个是单词的结尾。

具体实现如下：
先初始化遍历的指针 $p=0$ 在根节点，然后跑文本串，让 $p$ 取到这一个节点的数，也就是 $ch_{p,x}$，其中 $x=s_i-97$，然后跑这棵树。$j$ 从 $p$ 开始，当 $j$ 没有爬到根，也就是 $j\neq 0$ 时，且当前节点的 $cnt_j$ 是没计算过的，就让 $ans+cnt_j$，然后把 $cnt_j$ 标记为

，这里标记为 $-1$ 是因为如果标记为 $0$ 的话，有时可能会少统计。
最后 $ans$ 就是答案。

拓扑排序优化

AC自动机有一个非常牛的技巧，叫做拓扑排序优化。

AC自动机如果每次暴力跳 fail 的话，在一些类似“金字塔”的数据，也就是每个字符一样，第一个模式串长度是 $1$，第二个是 $2$，以此类推。在这样的数据中，如果每次都暴力跳 fail 的话，就会被卡成 $O(n^2)$ 导致超时。

在建 fail 时，把 fail 连成边，变成一棵 fail 树。所以可以将问题转换：在 fail 树上求链的长度。
在这时，有一个优化方法，就是用拓扑排序中的拓扑序来跑这个树。
在建 $fail$ 的过程中，如果没有这个节点，就进行一个记忆化的操作，让 $ch_{p,i}=ch_{fail_p,i}$ 把这个点连上。这其实就是一个建字典图的过程。
因为如果跑一个都是一个字符的链的 fail，会发现每次一个节点的结果上传，上面的数都会增加。所以可以从最底部开始向上做一个类似前缀和或者拓扑排序 DP 的操作，将子树的 cnt 向上传递。时间复杂度优化为严格 $O(n)$。

实现其实非常简单。拓扑排序的入度统计在建 $fail$ 时，在满足有边时把 $fail_{ch_{p,i}}$ 的入度加 $1$ 即可。
注意在建字典树时，在跑完模式串之后不需要更新 $cnt[p]$，只用 $ed_{id}=p$，其中 $ed_i$ 表示在第 $i$ 个单词结尾的编号，$id$ 在建树时把 $i$ 顺便传进来就可以。
那 $cnt$ 在哪更新呢？就要在写一个 $query$，其实本质上就是一个遍历。跑文本串，把当前这位的字符在字典树上的节点的 $cnt$ 加 $1$ 即可。
拓扑排序的过程和板子差不多，先将 $idx$ 个节点的字典树（其实是图）上的节点判断是不是入度为 $0$，如果是就入队。然后就是一个广搜的过程，在取出队头之后，将上面的节点拿到下面的节点的 $cnt$，也就是 $cnt_{fail_p}$ 加上 $cnt_p$，再让 $fail_p$ 这个节点的入度减 $1$。当 $cnt_{fail_p}$ 为 $0$ 时，就把它入队。

最后第 $i$ 个模式串的出现次数就是 $cnt_{ed_i}$。 注意点 1.注意在 bfs 时当满足 $ch_{p,i}\ge 0$ 时，处理完 $fail$ 之后要把 $ch_{p,i}$ 入队。
2.查询时 $cnt_j$ 统计完之后一定是标记为 $-1$，循环时的条件就是 $\sim cnt_j$，因为 $-1$ 的按位取反是 $0$。
3.注意字典树的建树操作时不要更新 $cnt$。
4.注意建 fail 和拓扑排序时更新入度的点，哪个是 $to$，哪个是 $from$。
5.注意要先跑 $query$ 再跑拓扑排序。

求主串中模式串出现次数(暴力跳fail)

P3808 AC 自动机（简单版）的代码。

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
int ch[N][26];
int n;
int cnt[N],idx;
int fail[N];
char c[N];
void insert(char *c){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!ch[p][x])ch[p][x]=++idx;
		p=ch[p][x];
	}
	cnt[p]++;
}
void bfs(){
	queue<int>q;
	for(int i=0;i<26;i++){
		if(ch[0][i]){
			q.push(ch[0][i]);
		}
	}
	while(q.size()){
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(ch[p][i]){
				fail[ch[p][i]]=ch[fail[p]][i];
				q.push(ch[p][i]);
			}
			else {
				ch[p][i]=ch[fail[p]][i];
			}
		}
	}
}
int query(){
	int ans=0;
	int p=0;
	for(int i=0;s[i];i++){
		p=ch[p][s[i]-'a'];
		for(int j=p;j&&~cnt[j];j=fail[j]){
			ans+=cnt[j];
			cnt[j]=-1;
		}
	}
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",c);
		insert(c);
	}
	bfs();
	scanf("%s",s);
	cout<<query();
	return 0;
}

求每个模式串在主串中出现的次数(拓扑排序优化)

P5357 【模板】AC 自动机 的代码。

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int ch[N][30];
char s[N];
char str[N];
int n;
int fail[N];
int rd[N];
int cnt[N],ed[N];
int idx;
void insert(char *c,int id){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!ch[p][x])ch[p][x]=++idx;
		p=ch[p][x];
	}
	ed[id]=p;
}
void bfs(){
	queue<int>q;
	for(int i=0;i<26;i++){
		if(ch[0][i]){
			q.push(ch[0][i]);
		}
	}
	while(q.size()){
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(ch[p][i]){
				fail[ch[p][i]]=ch[fail[p]][i];
				rd[fail[ch[p][i]]]++;
				q.push(ch[p][i]);
			}
			else {
				ch[p][i]=ch[fail[p]][i];
			}
		}
	}
}
void query(){
	int p=0;
	for(int i=0;s[i];i++){
		p=ch[p][s[i]-'a'];
		cnt[p]++;
	}
}
void topo(){
	queue<int>q;
	for(int i=1;i<=idx;i++){
		if(rd[i]==0)q.push(i);
	}
	while(q.size()){
		int p=q.front();
		q.pop();
		cnt[fail[p]]+=cnt[p];
		rd[fail[p]]--;
		if(rd[fail[p]]==0){
			q.push(fail[p]);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",str);
		insert(str,i);
	}
	scanf("%s",s);
	bfs();
	query();
	topo();
	for(int i=1;i<=n;i++){
		cout<<cnt[ed[i]]<<'\n';
	}
	return 0;
}

动态规划

背包DP

背包DP是 DP 中最基础的一种，比较好理解的，接下来介绍几种背包DP。

首先要了解背包DP解决的问题，就是类似于求给定一个可取价值和一些物品数量和单个价值，在各种约束下可以达到的最值。

01背包

属于最基础的了，但是其他背包基本都要建立在它身上。

01背包就是有 $n$ 物品，每个物品有它的价值 $v_i$ 和重量 $w_i$，你可以选总容量为 $W$ 的物品，但是每件物品只能选一件，求最大价值。

我们设 $f_{i,j}$ 表示选前 $i$ 个物品，最大容量为 $j$ 的最大价值。
这个数组的转移显然是 $f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$ 满足 $w_i\le j$。
这个转移了，求最大的两个数 $f_{i-1,j}$ 和 $f_{i-1,j-w_i}+v_i$ 分别是当前位置不取，取上一个位的值，和当前位置取，所以价值要减去 $w_i$，这里省略使用表格来理解的过程。
答案显然是 $f_{n,W}$。

这个转移是时间复杂度是 $O(nW)$，是优秀的，但是空间复杂度 $O(nW)$ 对比起来就是 shit。
考虑滚动数组优化空间。

设 $f_j$ 表示前 $j$ 的物品的最大价值。
转移其实和二维的一样，是 $f_j=\max(f_j,f_{j-w_i}+v_i)$ 且满足 $w_i\le j$。
在此处，可以省略掉第一位的原因就是因为第 $i$ 个数据只受 $i-1$ 的影响，所以可以滚动优化。
但是注意滚动优化的时候，第二层循环要从大至小遍历，不然的话有一些数据会多取几次。
因为是一维且从大到小，只有从 $W$ 循环到 $w_i$ 即可。
当然滚动数组也可以用两个数组来进行交换实现。
答案显然是 $f_W$。

空间复杂度 $O(W)$。

注意点
1.注意如果用二维的，第二次循环是有从小到大，而滚动数组的是从大到小
2.注意滚动是答案是 $f_W$，不要写成 $f_n$。
3.用二维数组的时候不要直接从 $w_i$ 遍历的 $W$，因为它是从小到大循环的。
4.$f$ 数组的大小要开 $\max W$。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int w[N],v[N];
int W,n;
int dp[20010];
int main(){
	cin>>W>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=W;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[W];
	return 0;
}

完全背包

完全背包就是有 $n$ 物品，每个物品有它的价值 $v_i$ 和重量 $w_i$，你可以选总容量为 $W$ 的物品，每件物品可以拿任意次，求最大价值。

完全背包和01背包的区别就在于可以取多次。

这里只讲述滚动优化的，朴素的以后在补。

设 $f_j$ 表示前 $j$ 的物品的最大价值。
转移：$f_j=\max(f_j,f_{j-w_i}+v_i)$ 且满足 $w_i\le j$。
这时你会发现：这个东西不是和01背包的长得完全一样吗？
确实是。
但是，不同点就在于怎么遍历取更新这一个 $f$ 数组。
在01背包中，我们说了，01背包的第二层循环要倒序遍历，因为正序遍历有一些数据会多计算，而这正好符合了完全背包的做法，所以只需要将循环从 $w_i$ 到 $W$ 即可。

时间复杂度 $O(nW)$，空间复杂度 $O(W)$。 注意点 注意要正序遍历。
其他同01背包。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int w[N],v[N];
int W,n;
int dp[20010];
int main(){
	cin>>W>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=W;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[W];
	return 0;
}

多重背包

多重背包就是有 $n$ 物品，每个物品有价值 $v_i$ 和重量 $w_i$，还有数量 $s_i$，你可以选总容量为 $W$ 的物品，每件物品最多可以拿 $s_i$ 个，求最大价值。

先考虑朴素做法。

发现这一个问题可以拆成多个01背包来解决，就是把第 $i$ 种物品拆分成 $c_i$ 种只有一个的物品的01背包去做。

时间复杂度貌似是枚举每一个重量的和拆01背包的 $O(V\sum c_i)$。

太慢了，考虑优化。

使用二进制分组优化，因为每一个正整数都可以表示为一个二进制，我们可以反推过来，用 $\log n$ 个二进制表示从 $0$ 到 $c_i$ 的任何数，将 $c_i$ 是用二进制拆分，得到的结果去算贡献替换掉 $w_i$ 和 $v_i$ 中的值，就可以做到很快的速度处理多重背包了。

时间复杂度 $O(nm\log V)$。

还有一种使用单调队列优化的空间 $O(nm)$ 的做法，等我学了再写。

注意点
1.注意二进制分组的剩余的值要特殊处理。

code

朴素做法：

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=10100;
int w[N],v[N],s[N];
int W,n;
int dp[N];
int main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i]>>s[i];
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=s[k];i++){
			for(int j=W;j>=w[k];j--){
				dp[j]=max(dp[j],dp[j-w[k]]+v[k]);
			}
		}
	}
	cout<<dp[W];
	return 0;
}

二进制优化：

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int w[N],v[N],s[N];
int W,n;
int dp[N];
int cnt;
int vi,wi,si;
int main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++){
		cin>>wi>>vi>>si;
		int k=1;
		while(k<=si){
			cnt++;
			w[cnt]=wi*k;
			v[cnt]=vi*k;
			si-=k;
			k*=2;
		}
		if(si){
			cnt++;
			w[cnt]=wi*si;
			v[cnt]=vi*si;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=W;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[W];
	return 0;
}

分组背包

分组背包就是有 $n$ 组物品，每组物品有 $s_i$ 个，第 $s_i$ 里的第 $j$ 个物品有价值 $v_{i,j}$ 和重量 $w_{i,j}$，每组至多可以拿一个，求在可以拿 $W$ 个的情况下的最大价值。

发现本题可以直接把每组拆成01背包去做，每一次在里面多跑一个 $s_i$ 组的东西，然后直接模版就行了，

时间复杂度貌似是 $O(nV\max s_i)$，空间复杂度貌似是 $O(V+n\max s_i)$。

注意点
1.注意跑01背包时的转换模板中的 $v_i$ 和 $w_i$。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N][N],w[N][N],s[N];
int dp[N];
int n,W;
int main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		for(int j=1;j<=s[i];j++){
			cin>>v[i][j]>>w[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=W;j>=0;j--){
			for(int k=1;k<=s[i];k++){
				if(j>=v[i][k]){
					dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
				}
			}
		}
	}
	cout<<dp[W];
	return 0;
}

图论

拓扑排序

学了AC自动机的拓扑排序优化，故来补一下。

拓扑排序是一种在DAG(有向无环图)上求解关于先后顺序的算法。其中它排序出来的结果叫做拓扑序。

拓扑排序其实可以抽象化成家谱：给定每个人的子辈，求所有人的辈分排序。

拓扑排序本质上就是一个 bfs。
首先遍历所有点，把入度为 $0$ 的点找出来，不难证明，这些点就是最高辈分的那些点，因为他们都没有父节点。把这些点入队，然后跑 bfs，将队头的点取出来，此时队头这个点，输出。此时做一个类似删点的操作，遍历这个点的所有邻居，因为这个点被删了，所以把它邻居的入度全部减 $1$。此时入度变成 $0$ 的点就入队，跑到结束为止。
删点只需处理入度。 注意点 1.不可以动这个图，删点只是名义上的，不是真的删，只需要处理入度就行了。
2.记得在输入时统计入度。
3.删完邻居边之后注意判入度和入队。

code

B3644 【模板】拓扑排序 / 家谱树

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
queue<int>q;
int in[N];
int n,m;
int ans[N],cnt;
void topo(){
	for(int i=1;i<=n;i++){
		if(!in[i]){
			q.push(i);
		}
	}
	while(q.size()){
		int u=q.front();
		cout<<u<<" ";
		q.pop();
		for(int ne:g[u]){
			in[ne]--;
			if(!in[ne]){
				q.push(ne);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int t;
		while(cin>>t&&t){
			g[i].push_back(t);
			in[t]++;
		}
	}
	topo();
	return 0;
}

最小生成树

Kruskal

Kruskal 求最小生成树是一种以边贪心的最小生成树算法。

设一张图的点数为 $n$，边数为 $m$。
观察一个图和它的最小生成树，发现在构造最小生成树的过程中，每一次是选择一条较小的边去连通，所以考虑贪心。
首先肯定是按边权从小到大排序，然后跑每一条边。如果这个边得起点和重点没有放进最小生成树的集中，就把他们放进集合，并将答案加入边权，总边数 $+1$。如果在跑的过程中，总边数达到 $n-1$，那么就说明这一个树构造好了，可以直接

break

此时的问题就是，这个最小生成树集怎么维护？这里可以使用并查集做到 $O(\alpha(n))$ 的每次操作，只有把每个点开到并查集里，每次判断这一条边的起点和终点是否在一个集合里，是的话跳过，不是的话就合并。

总复杂度为排序的 $O(m\log m)$。

注意点
1.排序是注意是 $m$ 而不是 $n$。
2.注意初始化并查集。

code

cpp
Copy
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+10;
struct node{
	int u,to;
	int w;
};
bool cmp(node a,node b){
	return a.w<b.w;
}
node e[N];
int n,m;
int fa[N];
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
void kruskal(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int ans=0;
	int cnt=0;
	for(int i=1;i<=m;i++){
		int u=e[i].u,to=e[i].to;
		int w=e[i].w;
		if(find(u)!=find(to)){
			//cout<<u<<' '<<to<<'\n';
			ans+=w;
			cnt++;
			merge(u,to);
			if(cnt==n-1)break;
		}
		
	}
	if(cnt<n-1)cout<<"orz";
	else cout<<ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].to>>e[i].w;
	}
	sort(e+1,e+m+1,cmp);
	//for(int i=1;i<=m;i++)cout<<e[i].w<<' ';
	//cout<<'\n';
	kruskal();
	return 0;
}

Prim

以后再补。

树的重心

树的重心就是在一个树里，删去一个节点，使剩下的最大联通快最小。
我们要在 $O(n)$ 的时间内，求出这个重心。

如果每一个节点当根，每一个都跑一遍 dfs 的话，时间复杂度是 $O(n^2)$，显然不可以通过。

所以就要用到一个技巧：换根。
首先，我们要用 dfs 求出以 $1$ 为根的每个节点的子树大小和父节点。然后就是换根环节了，随便观察一个树以 $1$ 为根时的每个节点的子树大小，会发现：当换成 $x$ 点为根时，如果原来的根是 $fa_x$ 点，只有 $x$ 和 $fa_x$ 的子树大小会改变，而点 $x$ 的子树大小会变成 $n$，$fa_x$ 的子树大小会变成 $n-size_x$，其中 $size_i$ 表示 $i$ 的子树大小。

这个写出来之后，就只用把邻居跑一遍，满足条件的就取换根之后的 $\max$，否则直接取 $size_{ne}$。
多个重心只用求完一个重心后，每个点跑一下，如果删去这个点的重心等于已经求了的重心，就放入答案序列中。

注意点
1.在处理换根时，不可以真正的换根！！！ 只要取个 $\max$ 就行了。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
int n;
int sz[N];
int fa[N];
void dfs(int u,int f){
	sz[u]=1;
	fa[u]=f;
	for(auto ne:g[u]){
		if(ne==f)continue;
		dfs(ne,u);
		sz[u]+=sz[ne];
	}
}
int k[N];
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		for(auto ne:g[i]){
			if(ne==fa[i])mx=max(mx,n-sz[i]);
			else mx=max(mx,sz[ne]);
		}
		if(mx<ans){
			ans=mx;
			mi=i;
		}
	}
	int t=0;
	for(int i=1;i<=n;i++){
		int mx=-1;
		for(auto ne:g[i]){
			if(ne==fa[i])mx=max(mx,n-sz[i]);
			else mx=max(mx,sz[ne]);
		}
		if(mx==ans){
			k[++t]=i;
		}
	}
	sort(k+1,k+t+1);
	for(int i=1;i<=t;i++){
		cout<<k[i]<<' ';
	}
	return 0;
}

树的直径

树的直径就是树上两点的最远距离。

如果暴力 dfs 会发现，最后情况下每一次都把树跑满，时间复杂度 $O(n^2)$，显然是不可以通过 $10^5$ 的数据的。
考虑优化成 $O(n)$。

假设有一点 $x$，通过一次 $O(n)$ 的 dfs 找到了自己的最远的是 $y$，此时发现，如果再跑一次以 $y$ 为起点的 dfs，这个 dfs 中的跑的距离就是答案了。

注意点
1.实现时 dfs 中的边界。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
int n;
bool vis[N];
int ans;
int sum;
int a,b;
void dfs(int u,int cnt){
	if(cnt>sum){
		sum=cnt;
		ans=u;
	}
	vis[u]=1;
	for(auto ne:g[u]){
		if(!vis[ne]){
			dfs(ne,cnt+1);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	a=ans;
	sum=ans=0;
	memset(vis,0,sizeof vis);
	dfs(a,0);
	cout<<sum;
	return 0;
}

数学

快速幂

快速幂是很多数学题的最基本的东西，是一种可以在 $O(\log n)$ 的复杂度求解 $a^n$ 的问题的算法。

一般来说，求解 $a^n$ 的问题要循环 $n$ 次，每次乘 $a$，时间复杂度 $O(n)$。
但是快速幂用到了一个性质：任何一个正整数都可以写成几个 $2$ 的次幂的和，其实就是可以转换成二进制。
所以可以将 $a^n$ 转换成：

则 $a^n$ 变为：

剩下的预处理解决即可，也可以边做边出来。

因为 $t\le \log n$，所以时间复杂度是 $O(\log n)$。

注意点
1.注意取模，取模不当很容易爆。

code

P1226 【模板】快速幂

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll a,ll b,ll p){
	ll ans=1;
	a%=p;
	while(b){
		if(b&1){
			ans*=a%p;
			ans%=p;
		}
		a=a*a%p;
		a%=p;
		b>>=1;
	}
	return ans;
}
int main(){
	ll a,b,p;
	cin>>a>>b>>p;
	cout<<a<<'^'<<b<<" mod "<<p<<'='<<qpow(a,b,p);
	return 0;
}

逆元

逆元的诞生是源于除法没有同余定理。

逆元的定义：在模意义下，一个数 $a$ 除以 $b$，等于乘 $b$ 的逆元。

首先我们要知道什么是同余定理。其实就是针对取模的运算的基本原理：
当 $a\equiv b\pmod m,c\equiv d\pmod m,m>0$ 时：

当 $a\equiv b\pmod m,m>0,k>0$ 时：

这时候注意，这些公式里面没有除法，说明除法是不一定满足的。这时就引出了逆元。
逆元其实就是把模意义下的除法变成乘法，对于一个正整数 $a$，它的逆元 $inv$ 与它的乘积在模 $m$ 的意义下为 $1$，也就是 $a\times inv=1\pmod 1$，$inv$ 也可以用 $a^{-1}$ 表示。这个时候就会发现：这个逆元不就是倒数吗？确实是，但是我们是要转换成乘法，倒数还是一个分数，也就是除法，是没什么意义的。

那怎么求 $a$ 的逆元呢，有以下方法。

费马小定理

由费马小定理可知：

使用快速幂解决即可，时间复杂度 $O(\log p)$，但是求 $n$ 个数的逆元的复杂度是 $O(n\log p)$，不够快。

线性递推

我们设 $g_x$ 表示 $x!$ 在模 $m$ 意义下的逆元，$f_x$ 表示 $x$ 的阶乘。其中 $x!=\prod^x_{i=1}i$，其实就是 $x$ 的阶乘。

$f_i$ 显然可以用递推 $f_i=f_{i-1}\times i$ 来解决。问题是怎么求解 $g_i$？
这里给出一个要证明的结论：

右边的 $i!$ 与 $i$ 消掉变成 $(i-1)!$，所以等式成立。
所以可以先用费马小定理 $O(\log p)$ 的求出 $g_n$，剩下的直接从 $n$ 开始逆推回来。

求出了 $x!$ 的逆元，接下来就是求 $x$ 的逆元。
设 $i$ 的逆元为 $inv_i$，还是给出要证明的结论：

$i!\times (i-1)!$ 显然等于 $i$，所以等式成立。

这样就可以用线性离线处理出 $1$ 到 $n$ 的逆元了。时间复杂度 $O(n+\log p)-O(1)$。 注意点
1.递推求阶乘时注意 $0!=1$ 这个边界。
2.推阶乘逆元的递推是从大到小。

code

P3811 【模板】模意义下的乘法逆元

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=5e6+10;
ll n;
ll p;
ll qpow(ll a,ll b,ll p){
	ll res=1;
	a%=p;
	while(b){
		if(b&1){
			res=res*a%p;
		}
		a=a*a%p;
		b>>=1;
	}
	return res;
}
ll inv[N];
ll fact[N];
void init(int n){
	fact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=fact[i-1]*i%p;
	}
	int k=qpow(fact[n],p-2,p);
	inv[n]=k;
	for(int i=n;i>=1;i--){
		inv[i-1]=inv[i]*i%p;
	}
	for(int i=1;i<=n;i++){
		cout<<inv[i]%p*fact[i-1]%p<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>p;
	init(n);
	return 0;
}

组合数

从 $1,2,3,...,n$ 中选择 $m$ 个数的方案数，记为 $\dbinom{n}{m}$，也可记为 $C^m_n$。读作 “$n$ 取 $m$”。$\dbinom{n}{m}=\frac{n!}{m!(n-m)!}$

$O(n^2)$

引理：在杨辉三角中的第 $n$ 行 $m$ 列等于 $\dbinom{n}{m}$。
根据这个引理，我们可以用构造杨辉三角的形式构造组合数。
杨辉三角的构造很简单，就是当前位等于上面的加左上的，也就是 $a_{i,j}=a_{i-1,j}+a_{i-1,j-1}$，转换成组合数就是 $\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$。

时间复杂度 $O(n^2)$。

注意点
1.注意边界 $\dbinom{0}{0}=1$。

code

B2164 组合数问题

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=5050,mod=1e9+7;
int c[N][N];
void get_c(int n){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(!j)c[i][j]=1;
			else c[i][j]=c[i-1][j]+c[i-1][j-1];
            c[i][j]%=mod;
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	get_c(max(n,m));
	cout<<c[n][m]%mod;
	return 0;
}

$O(n)$

展开 $\dbinom{n}{m}=\frac{n!}{m!(n-m)!}$，发现这个式子可以直接使用阶乘求解，但是答案一般都很大，除法又正好不满足同余定理，所以这时，要用逆元来解决。

由逆元的定义可得 $\dbinom{n}{m}=n!\times inv_{m!}\times inv_{(n-m)!}$，所以只要预处理 $1$ 到 $n$ 的阶乘逆元，最终答案就是 $n!\times inv_{m!}\times inv_{(n-m)!}$。

时间复杂度 $O(n+\log p)-O(1)$。 注意点
1.注意在求组合数时可以模，因为转换成了逆元。

code

B3717 组合数问题

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int n,m;
typedef unsigned long long ll;
const ll mod=998244353;
ll qpow(ll a,ll b,ll p){
	ll res=1;
	a%=p;
	while(b){
		if(b&1){
			res=res*a%p;
		}
		a=a*a%p;
		b>>=1;
	}
	return res;
}
int T,Q;
ll inv[N];
ll fact[N];
void init(int n){
	fact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=fact[i-1]*i%mod;
	}
	int k=qpow(fact[n],mod-2,mod);
	inv[n]=k;
	for(int i=n;i>=1;i--){
		inv[i-1]=inv[i]*i%mod;
	}
}
ll C(ll n,ll m){
	return fact[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T>>Q;
	init(Q);
	ll res=0;
	while(T--){
		cin>>n>>m;
		res^=C(n,m);
	}
	cout<<res;
	return 0;
}

二项式定理

我们早就学过，杨辉三角的第 $n$ 行就是 $(a+b)^n$ 的展开式的各项系数，所以我们可以根据杨辉三角和组合数的关系，推出如下式子：

这个展开式首先就要把每一位加上，所以要用求和。$\dbinom{n}{i}$ 表示的是杨辉三角第 $n$ 行的第 $i$ 个数，也就是这一位的系数。因为 $(a+b)^n$ 的每一项的指数和都是 $n$，且 $a$ 的指数逐渐减少， $b$ 的指数是逐渐增大。注意可以 $i=0$，因为有 $a^0=b^0=1$ 作为系数，省略。

容斥原理

计数最基础的东西。
首先我们要知道什么是计数。
集合 $A$ 的计数用 $|A|$ 表示，计数的严格表示就是：

其实就是集合 $A$ 中的元素个数。

容斥原理就是它的字面意思，容表示加，斥表示减，所以容斥原理就是加加减减。我们都学过，如果两个没有交集的集合 $A$ 和 $B$ 取并集的计数就是直接讲两个集合的计数相加，也就是 $|A \cup B|=|A|+|B|,A\cap B=\varnothing$，这个称为加法原理。同样的 $|A\times B|=|A|\times |B|$，这个被称为乘法原理。

我们可以注意到，在刚刚的加法原理中，有一个条件是 $A\cap B=\varnothing$，当时如果 $A\cap B\ne \varnothing$ 呢？这个时候就要用容斥原理了。

一般来说，求集合的交集比就集合的并集简单，所以容斥原理就是把并集转为交集。 最经典的就是有两个圆，他们有重叠部分，知道两个圆的面积和重叠面积，求总面积。这个问题的答案显然是把连个面积加起来，再把重叠面积相减。用集合来表示的话，就是

同样也通用于刚刚的加法原理。
类似的，三个集合的并集就是把每个面积加起来，再把每两个集的交集减去，这是发现中间的三个集合的交集减多了，所以要加回去。表示为：

容斥原理其实就是把这个式子推广到一般情况。

设有 $n$ 个集合，第 $i$ 个集合叫做 $A_i$，则：

其中容和斥的部分分别是：

但是偶尔会出现求并集比求交集难容易的情况。
这是就要用到容斥原理的交集转并集。
设有 $n$ 个集合，第 $i$ 个集合叫做 $A_i$，$K=\{1,2,\cdot\cdot\cdot,n\}$，$U$ 表示总集，则：

质数筛

质数筛也是数论中非常重要的一个部分。

根号筛

这个是很多人第一个学的筛法，也是最简单的筛法。

做法很简单，就是枚举 $2$ 到 $n-1$ 里所有的数，如果当前数可以被 $n$ 整除，那么 $n$ 显然就是一个和数。直到跑完循环也没返回，就说明 $n$ 是一个指数。当然，$n<2$ 要特判，$n=2$ 也要特判。这样做每次判断一个数的时间复杂度是 $O(n)$，判断 $n$ 个数的时间复杂度是 $O(n^2)$。太慢了，要优化。

发现每当枚举的数 $\ge \sqrt n$ 时，这个数就已经被判断过了，所以只需要枚举 $2$ 到 $\sqrt n$ 的数就可以了，判断一个数的时间复杂度是 $O(\sqrt n)$，判断 $n$ 个数的时间复杂度是 $O(n\sqrt n)$。 注意点
1.注意循环到 $\sqrt n$ 时，不建议直接用

sqrt(n)

i*i<=n

i<=n/i

code

这里只给出判断的函数。

cpp
Copy
bool isprime(int x){
	if(x<2)return 0;
	if(x==2)return 1;
	for(int i=2;i<=x/i;i++){
		if(x%i==0)return 0;
	}
	return 1;
}

埃筛

埃筛，也叫埃氏筛，全称埃拉托斯特尼筛法。是一种高效的判断质数的筛法。

原理是这样的：因为每一个的倍数都是合数，所以可以从 $2$ 开始筛，如果当前的数标记为质数，就把它的倍数标成合数，如果是合数则直接跳过。埃筛的数也只需要枚举到 $\sqrt n$。
最后筛出来的标记数组就是每个数是质数还是合数的情况。
筛 $n$ 个数的时间复杂度是 $O(n\log\log n)$，我也不知道怎么证。

值得一提的是，因为埃筛只用一个

bool 

bitset

bool

bitset<N>prime

bitset<int>prime[N]

bitset<bool>prime[N]

code

如果使用

bool

bitset<N>prime;

bool prime[N];

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10;
int n,q;
bitset<N>prime;
int primes;
int cnt=0;
void init(int n){
	for(int i=2;i<=n/i;i++){
		if(prime[i])continue;
		for(int j=i+i;j<=n;j+=i){
			prime[j]=1;
		}
	}
	for(int i=2;i<=n;i++){
		if(!prime[i])cnt++;
	}
	cout<<cnt;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	init(n);
	return 0;
}