NOIP
zhouwc
2018-11-07 14:05:03
[toc]
# 数学相关
### 快速幂
快速幂通过二进制分解来快速求$a^b$的值，由于$a^b$的值很大，所以一般会带有模数。
```cpp
ll fast_pow(ll x,ll n,ll mod){
ll ret=1;
for(ll p=1;p<=n;p<<=1,x=x*x%mod)
if(n&p) ret=ret*x%mod;
return ret;
}
```
快速幂可以推广到一切符合结合律的运算中（如：加法，矩阵乘法）。
### 欧拉筛
欧拉筛具体可以参见：[这篇文章](http://zwcblog.top./zwc/%E6%AC%A7%E6%8B%89%E7%AD%9B%E6%B3%95%E6%B1%82%E8%B4%A8%E6%95%B0%E4%B8%AA%E6%95%B0%E5%92%8C%E8%B4%A8%E6%95%B0%E5%92%8C/)
欧拉筛保证每个合数均被其除自身以外最大的因数筛掉。能在O(n)的时间内求出1～n中所有的质数。线性筛还可用于求1～n中积性函数的值或者快速分解质因数。
```cpp
void Euler(int n){
for(int i=1;i<=n;++i) vis[i]=false;
for(int i=2;i<=n;++i){
if(!vis[i]) prime[++top_prime]=i;
for(int j=1;j<=top_prime&&i*prime[j]<=n;++j){
vis[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
```
### 辗转相除法（欧几里得算法）
欧几里得算法可用于求两个正整数的最大公约数。欧几里得算法通过等式gcd(a,b)=gcd(b,a%b)来递归求解，由于每层递归后a* b的值会至少减少一半，所以欧几里得算法的时间复杂度为$O(lg(a* b))$。
```cpp
int gcd(int a,int b){
while(b!=0) a%=b,swap(a,b);
return a;
}
```
### 扩展欧几里得（ex_gcd)
扩展欧几里得用于求方程ax+by=gcd(a,b)的一组整数解，通常可用于求乘法在模意义下的逆元。时间复杂度与欧几里得算法相同。
```cpp
void ex_gcd(ll& x,ll& y,ll a,ll b){
if(b==0){
x=1,y=0;
return;
}
ex_gcd(y,x,b,a%b);
y-=a/b*x;
}
```
### 欧拉定理
欧拉定理:对于a,p互质，有$a^{varphi(p)}equiv 1(mod p)$其中$varphi(p)$表示1到p中与p互质的数的个数。
不难发现，费马小定理只是欧拉定理的一个特殊情况。
我们不妨设1到p中与p互质的数从小到大分别为：$b_1,b_2,b_3,...,b_varphi(p)$
【引理1】$ab_1,ab_2,ab_3,...,ab_{varphi(p)}$在模p意义下互不相等。
证：假设该结论不成立，则可必定存在$ab_nequiv ab_m(mod p),1le mle nle varphi(p)$。
则$a(b_n-b_m)equiv 0(mod p)$
由于a与p互质，$b_n$与$b_m$均小于p且不相等，所以该式不可能成立。
引理1证毕。
【引理2】$ab_1,ab_2,ab_3,...,ab_{varphi(p)}$均与p互质。
证：对于第i项，由于a与p互质，$b_i$与p互质，所以它们的乘积与p互质。证毕。
【引理3】$lbrace ab_1mod p,ab_2mod p,...,ab_{varphi(p)}mod p rbrace= lbrace b_1,b_2,...,b_{varphi(p)} rbrace$
证：由引理1和引理2易得。
【欧拉定理】$a^{varphi(p)}equiv 1(mod p)$
证：由引理3得，两个集合中的元素能一一对应，则它们的乘积相等，即：
$ab_1ab_2...ab_{varphi(p)}equiv b_1b_2...b_{varphi(p)}(mod p)$，将右边的除到左边去，可得：
$a^{varphi(p)}equiv 1(mod p)$，即欧拉定理得证。
使用欧拉定理加上快速幂可以快速求出逆元。
### 合并模线性方程
合并模线性方程用于求解模线性方程组。这个方程组中每一个方程都是这种形式的：$xequiv a_i (%b_i)$。可以通过等式$a_1+b_1y_1=a_2+b_2y_2$来求出一组$y_1,y_2$的解来进行合并。
```cpp
bool merge_equ(ll a1,ll b1,ll a2,ll b2,ll& a3,ll& b3){
ll y1,y2,k=gcd(b1,b2);
if((a2-a1)%k!=0) return false;
ex_gcd(y1,y2,b1,b2);
b3=b1/gcd(b1,b2)*b2;
y1=(a2-a1)/k*y1%b3;
a3=((b1*y1+a1)%b3+b3)%b3;
return true;
}
```
该函数将结果存入a3和b3，返回值表示这个方程组是否有解。
### 组合数相关
#### 线性求逆元
线性求逆元算法可以在O（n）时间内求出1～n中所有数在模MOD意义下的逆元。线性求逆元基于下列等式：
$i^{-1}=(MOD-MOD/i)(MOD%i)^{-1}$
证明：
令$ai+bequiv 0$
两边同乘$a^{-1}b^{-1}$有
$ab^{-1}+i^{-1} equiv 0$
因此得证。
#### 快速求组合数
通过线性求逆元预处理出$i!$和$(i!)^{-1}$，快速求组合数。
```cpp
int c(int n,int m,int mod){
if(n<m||n<0||m<0) return 0;
return (ll)fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;
}
void init_fac(int n,int mod){
inv[1]=fac[0]=fac_inv[0]=1;
for(int i=2;i<=n;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%mod;
for(int i=1;i<=n;++i) fac_inv[i]=(ll)fac_inv[i-1]*inv[i]%mod;
}
```
#### lucas定理
lucas定理用于快速求$C_n^m %p$的值，其中n,m很大，但是p是质数并且不是很大。
lucas定理：$C_n^m equiv C_{n/p}^{m/p} C_{n%p}^{m%p}$
证明：
设n=ap+b,m=cp+d，则：
$$C_n^m equiv frac{(ap+b)!}{(cp+d)!((a-c)p+(b-d))!} $$
$$ equiv frac{a! (p!)^a b! } { c! (p!)^cd! (a-c)(p!)^{a-c}(b-d)!}$$
$$ equiv C_{n/p}^{m/p} C_{n% p}^{m% p} $$
```cpp
int lucas(ll n,ll m,int mod){
if(n<mod&&m<mod) return c(n,m,mod);
else return (ll)c(n%mod,m%mod,mod)*lucas(n/mod,m/mod,mod)%mod;
}
```
### 离散化
离散化也是OI比赛中常用的技巧之一，这里由站长为大家写出。
由于b数组很大，但是我们不需要知道他的具体数值只要知道大小关系。这个时候我们可以对B数组进行离散化，代码见下。
**input**
```cpp
5
999 888 777 66 555
```
**output**
```cpp
5
5 4 3 1 2
```
**code**(by 劲大爷)
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
for (int i=1;i<=n;i++) t[++num]=a[i];
sort(t+1,t+num+1);
num=unique(t+1,t+num+1)-t-1;
for (int i=1;i<=n;i++) a[i]=lower_bound(t+1,t+num+1,a[i])-t;
}
```
# 字符串算法
### KMP算法
KMP算法通过nxt指针来进行快速匹配，可以在O（n）的时间内求出nxt数组，并在O（n）的时间内完成字符串匹配。代码中输出了所有匹配位置：
```cpp
template<typename T>
void get_nxt(T* a,int n,int* nxt){
nxt[0]=-1;
for(int i=1;i<=n;++i){
int j=nxt[i-1];
while(j!=-1&&a[j+1]!=a[i]) j=nxt[j];
nxt[i]=j+1;
}
}
template<typename T>
void match(T* a,T* b,int* nxt,int n,int m){
for(int i=1,j=1;i<=n;++i,++j){
if(a[i]!=b[j]){
while(j!=0&&a[i]!=b[j]) j=nxt[j-1]+1;
}else if(j==m){
printf("%dn",i-m+1);
j=nxt[j];
}
}
}
```
### manacher算法
manacher算法用于求一个字符串中以每一个位置为中心的最大回文半径。其通过对称性进行快速求解，在摊还O(n)的时间复杂度内完成求解。模板：
```cpp
template<typename T>
void manacher(T* a,int n,int* r){
int p=1; r[1]=1;
for(int i=2;i<=n;++i){
if(i<p+r[p]&&r[p+p-i]<p+r[p]-i){
r[i]=r[p+p-i];
}else{
r[i]=p+r[p]-i,p=i;
while(i-r[i]>=1&&i+r[i]<=n&&a[i+r[i]]==a[i-r[i]])
++r[i];
}
}
}
```
# 数据结构
### ST表
ST表可用于求解静态区间最大最小值查询问题。其预处理时间为O(nlgn)，空间复杂度为O(nlgn)，查询时间复杂度为O(1)。ST表也可以推广到一切可以重复计算的区间问题中（如区间gcd）。
```cpp
template<typename T,typename Func>
class STTable{
T st[23][MAX_N];
int p[MAX_N];
Func func;
public:
T& operator[](int x) { return st[0][x]; }
void build(int n){
for(int l=1;l<=20;++l)
for(int i=1;i<=n-(1<<l)+1;++i)
st[l][i]=func(st[l-1][i],st[l-1][i+(1<<l-1)]);
p[1]=0;
for(int i=2;i<=n;++i) p[i]=p[i>>1]+1;
}
T query(int l,int r){
int level=p[r-l+1];
return func(st[level][l],st[level][r-(1<<level)+1]);
}
};
```
### 树状数组
树状数组的本质是二项树森林，其可以快速计算1～x的区间和，可用于求解所有以1为起点的区间问题（求逆序对，求区间和等）。通过差分之类的操作可以解决更多问题。
```cpp
template<typename T,typename Func,T base>
class BinaryIndexTree{
T c[MAX_N];
int top;
Func func;
public:
void clear(int n){
top=n;
for(int i=1;i<=n;++i) c[i]=base;
}
void add(int x,T key){
for(;x<=top;x+=x&-x) c[x]=func(c[x],key);
}
T query(int x){
T ret=base;
for(;x>0;x-=x&-x) ret=func(ret,c[x]);
return ret;
}
};
```
#### 树状数组应用——求逆序对
最近求逆序对的题目有很多，所以站长为大家整理了一下树状数组求逆序对的方法（包含离散化）
```cpp
#include<bits/stdc++.h>
using namespace std;
int tot,a[1000005],b[1000005],c[1000005],d[1000005],n;
long long ans;
int lowbit(int x)
{
return x & -x;
}
void add(int x)
{
for (int i=x;i<=n;i+=lowbit(i))
c[i]++;
}
int Sum(int x)
{
long long ans=0;
for (int i=x;i>0;i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
for (int i=1;i<=n;i++)
a[++tot]=b[i];
sort(a+1,a+tot+1);
int num=unique(a+1,a+tot+1)-a-1;
for (int i=1;i<=n;i++)
b[i]=lower_bound(a+1,a+num+1,b[i])-a;
for (int i=n;i>=1;i--)
{
add(b[i]);
ans+=Sum(b[i]-1);
}
printf("%lldn",ans);
}
```
### 线段树
#### 常规线段树
常规线段树可用于处理大多数区间问题。实现线段树要求维护的键值可合并并且打标记后能快速更新键值。但是时间复杂度的常数较大，而且要开4倍空间。线段树写法的变化很多，所以不建议写成template，以洛谷P3373为例贴一下我的代码：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N=5+1e5;
typedef long long ll;
ll mod;
class SegmentTree{
struct Node{
ll sum,tag1,tag2;
}tree[MAX_N<<2];
inline void put_tag(int l,int r,int p,ll tag1,ll tag2){
tree[p].sum=(tree[p].sum*tag1+tag2*(r-l+1))%mod;
tree[p].tag1=tree[p].tag1*tag1%mod;
tree[p].tag2=(tree[p].tag2*tag1+tag2)%mod;
}
inline void down(int l,int r,int p){
int mid=l+r>>1;
put_tag(l,mid,p+p,tree[p].tag1,tree[p].tag2);
put_tag(mid+1,r,p+p+1,tree[p].tag1,tree[p].tag2);
tree[p].tag1=1,tree[p].tag2=0;
}
inline void up(int p){
tree[p].sum=tree[p+p].sum+tree[p+p+1].sum;
}
public:
void build(int p,int l,int r){
tree[p]=(Node){0,1,0};
if(l==r) return;
int mid=l+r>>1;
build(p+p,l,mid);
build(p+p+1,mid+1,r);
}
void change(int p,int l,int r,int x,int y,ll tag1,ll tag2){
if(l==x&&r==y){
put_tag(l,r,p,tag1,tag2);
return;
}
int mid=l+r>>1;
down(l,r,p);
if(y<=mid) change(p+p,l,mid,x,y,tag1,tag2);
else if(x>mid) change(p+p+1,mid+1,r,x,y,tag1,tag2);
else change(p+p,l,mid,x,mid,tag1,tag2),
change(p+p+1,mid+1,r,mid+1,y,tag1,tag2);
up(p);
}
ll query(int p,int l,int r,int x,int y){
if(l==x&&r==y) return tree[p].sum;
int mid=l+r>>1;
down(l,r,p);
if(y<=mid) return query(p+p,l,mid,x,y);
else if(x>mid) return query(p+p+1,mid+1,r,x,y);
else return (query(p+p,l,mid,x,mid)
+query(p+p+1,mid+1,r,mid+1,y))%mod;
}
}seg;
int main(){
int n,m; scanf("%d%d%lld",&n,&m,&mod);
seg.build(1,1,n);
for(int i=1;i<=n;++i){
int key; scanf("%d",&key);
seg.change(1,1,n,i,i,1,key);
}
while(m--){
int t,l,r; scanf("%d%d%d",&t,&l,&r);
if(t==1){
ll key;
scanf("%lld",&key);
seg.change(1,1,n,l,r,key,0);
}else if(t==2){
ll key;
scanf("%lld",&key);
seg.change(1,1,n,l,r,1,key);
}else{
printf("%lldn",seg.query(1,1,n,l,r));
}
}
return 0;
}
```
#### ZKW线段树
ZKW线段树将常规线段树自顶向下的遍历方式改成了自底向上，。ZKW线段树全部通过迭代的方式进行操作，由于这种写法相对于常规线段树还可以使用更多的位运算，因此可以大大降低常数，缩减代码长度。但也带来了标记难以处理和代码细节问题增多的问题，所以个人认为主要作用还是在不做区间修改的问题中。写一个单点修改，区间求最小值的代码：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N=5+1e5;
class ZKWSegmentTree{
int tree[MAX_N<<2],sz;
public:
void build(int* a,int n){
for(sz=1;sz<=n+2;sz<<=1);
for(int i=1;i<=sz+sz-1;++i) tree[i]=2e9;
for(int i=1;i<=n;++i) tree[i+sz]=a[i];
for(int i=sz+sz-1;i>1;--i) tree[i>>1]=min(tree[i>>1],tree[i]);
}
void change(int x,int key){
for(tree[x+=sz]=key;x>1;x>>=1)
tree[x>>1]=min(tree[x],tree[x^1]);
}
int query(int l,int r){
int ret=2e9;
for(l+=sz-1,r+=sz+1;l^r^1;l>>=1,r>>=1){
if(!(l&1)) ret=min(ret,tree[l^1]);
if(r&1) ret=min(ret,tree[r^1]);
}
return ret;
}
}seg;
int a[MAX_N];
int main(){
int n,m; scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
seg.build(a,n);
while(m--){
int t,x,y; scanf("%d%d%d",&t,&x,&y);
if(t==2) seg.change(x,y);
else printf("%dn",seg.query(x,y));
}
return 0;
}
```
评测机上运行时间比常规线段树快了1/4左右。
#### 动态开点线段树
动态开点线段树个人认为有两种。
第一种用于解决那些不需要初始化但是操作的下标值域范围非常大的问题。动态开点的基本思想是只把遍历到的点开出来。所以动态开点线段树需要将每个节点的两个儿子记下来，在每次down操作时开出新的节点，其它写法和常规线段树类似。
第二种类似于Trie树，用于解决一些在权值上的问题。这种写法可以理解为将每个元素二进制分解后看作一个01串然后丢入Trie树中，代码实现也和Trie树类似。可以用于插入删除，求前驱后继等，在一定程度上可代替平衡树。
动态开点线段树空间复杂度较高，容易被卡空间。
### 平衡树
平衡树一般指能让搜索树在较小时间界内完成其基本操作的数据结构，平衡树的应用非常广泛，C++STL中的很多东西都是使用红黑树（一种平衡树）来实现的。但是由于一般的平衡树代码冗长，难写难调，所以在OI中个人认为一般只会使用替罪羊树，树堆（treap）和伸展树（splay tree）。NOIP中在一些数据结构题在正解想不出来的情况下往往可以使用平衡树拿到高分（如去年D2T3）。可以戳[这里](http://zwcblog.top./4ccf99cf81c42233c714e9064d32a457/%e6%b5%85%e8%b0%88%e9%9d%9e%e6%97%8btreap/ "这里")来简单了解一下treap。
### 左偏树
一般的堆可以使用prioirty_queue来实现，但是如果需要涉及到合并操作就有点慢了，所以可以用左偏树来实现。
```cpp
struct LeftistTree{
struct Node{
int son[2],rank;
pair<int,int> key;
};
static Node heap[MAX_N];
static int top_heap;
int root;
static int new_node(pair<int,int> key){
heap[++top_heap]=(Node){{0,0},0,key};
return top_heap;
}
int merge(int x,int y){
if(x==0||y==0) return x+y;
if(heap[x].key>heap[y].key) swap(x,y);
heap[x].son[1]=merge(heap[x].son[1],y);
if(heap[heap[x].son[1]].rank>heap[heap[x].son[0]].rank)
swap(heap[x].son[0],heap[x].son[1]);
heap[x].rank=heap[heap[x].son[1]].rank+1;
return x;
}
LeftistTree(){ root=0; }
void insert(pair<int,int> key){
root=merge(root,new_node(key));
}
pair<int,int> top(){ return heap[root].key; }
void pop(){ root=merge(heap[root].son[0],heap[root].son[1]); }
};
LeftistTree::Node LeftistTree::heap[MAX_N];
int LeftistTree::top_heap=0;
```
### 并查集
并查集可以在$O(alpha(n))$的摊还时间内完成创建一个集合，合并两个集合，判断两个元素是否属于一个集合的操作。
```cpp
class DSF{
int fa[MAX_N],rank[MAX_N];
public:
void make_set(int x){
fa[x]=x,rank[x]=0;
}
int find_set(int x){
if(fa[x]!=x) fa[x]=find_set(fa[x]);
return fa[x];
}
void link(int x,int y){
if(rank[x]<rank[y]) swap(x,y);
fa[y]=x,rank[x]=max(rank[x],rank[y]+1);
}
bool member(int x,int y){
return find_set(x)==find_set(y);
}
void merge(int x,int y){
link(find_set(x),find_set(y));
}
}dsf;
```