知识点整理

heaven_soar · 2020-12-15 16:17:32 · 个人记录

（长期持续更新）

一、基本算法

搜索

——基本所有题都可使用

深度优先搜索(dfs)

——大量应用于暴力

常用递归实现，伪代码：

void/*返回值*/dfs(参数){
    if(临界条件){
        return;
    }
    递归调用
}

广度优先搜索(bfs)

队列实现，注意重复入队和入队条件。

常用于拓扑排序。

迭代加深(ID)

本质上是dfs和bfs的结合

规定递归层数，超出就返回。

启发式搜索(A*)

智能算法，无法确定复杂度，速度很快。

• 设当前状态到最终状态需要搜索次数函数g
• 规定一个启发函数 g' 为当前状态到最终状态理想需要搜索次数，g'\le g。
• 就可以按照g'进行优化搜索

启发式迭代加深搜索(IDA*)

顾名思义就是启发式搜索加迭代加深。

优化方法

• 记忆化：将搜索状态存储下来，减少搜索次数。

• 可行性剪枝：搜索某一步不成立，就不用往下搜索。

• 最优化剪枝：搜索到目前情况已经比已有答案劣，就不往下搜索。

排序

有大量排序方法，如插入排序，冒泡排序等。但多数因时间复杂度过高在OI中无人使用，下面只介绍两种常用的：

快速排序

原理是每次选一个元素，将小于它的放一边，大于它的放另一边，多次反复，直至有序。时间复杂度O(n\log n)。

algorithm头文件里有sort函数可以实现，就没人手打了。而且你常数还不一定有人家优

归并排序

本质是二分。先分下去，再合并回来。有些特殊题目中比快排快。

桶排序

建值域数组，将已有元素映射，复杂度O(m) m为值域。

贪心

正确定义为利用局部最优解代替全局最优解。时间复杂度：O(n \log n)因为基本都要排序。

几乎最难的算法，正解往往不易想到且很难证明。

但是贪心骗分方法一般还是能想到的。毕竟贪心是人的本能

分治

满足小范围解和大范围解有一定规律性，且扩大范围不会影响本来小范围的解的题目可以分治。

常见使用：二分。

二分查找

对于一个有序序列进行的查找，因为有序，可以通过中间值来缩小查找范围，直至搜索到。

伪代码：

int l=最小位置,r=最大位置,mid;
while(l<=r){
    mid=(l+r)>>1;
    if(a[mid]==ans) break;
    if(a[mid]<ans) l=mid=mid+1;
    else r=mid=mid-1;
}
/*mid即最终答案*/

以上代码判断加不加等号,更新为mid还是mid\pm 1都需要具体情况具体判断。

二分答案

对于一个最优答案如果满足单调性，就可以进行二分搜索。常见词汇：最大值最小、最小值最大。

两种写法，主要是看所求的是所有相同情况中的最后一个还是最前一个。 核心是保证转移后范围包含结果。

while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid)) l=mid;
    else r=mid-1;
}

while(l<r){
    int mid=(l+r)>>1;
    if(check(mid)) l=mid+1;
    else r=mid;
}

l为答案。

模拟

无需多讲，基本算法。

高精度

恶心东西。

基础为一位一压，可以改成四位一压、八位一压。

动态规划(Dynamic Programming，DP)

其实是一种解决问题思想：

• 考虑状态转移-->进行决策-->存储决策

通常由记忆化搜索和递推解决。

适用于之后决策不会影响之前决策（无后效性）。种类繁多，题目灵活，难度大。

可以增加维度来解决后效性的问题。

背包问题

经典dp问题。种类也很多。

描述：一个背包装物品，每种物品有一个价值和体积，在装得下的情况下求价值最大。

• 01背包：每种物品只有一个。

  若\large f_{i,j}表示当前枚举到第i个物品，已装背包容量是j的状态，有转移方程：

  \Large f_{i,j}=\max (f_{i-1,j},f_{i-1,j-v_i}+w_i)

  其中\large f_{i-1,j}表示这个物品不加入背包，\large f_{i-1,j-v_i}+w_i表示这个物品加入背包。

  可以进行循环数组减少一维空间复杂度。

  代码：

  for(register int i=1;i<=n;++i){
  for(register int j=m;j>=1;--j){//注意一定要从大到小枚举，原因手推一下就明白了
        if(j>=w[i])f[j]=Min(f[j-v[i]]+w[i],f[j]);
    }
  }

• 完全背包：每种物品有无限多个。

  转移方程：

  \Large f_{i,j}=\max (f_{i-1,j},f_{i,j-v_i}+w_i)

  也可以进行循环数组。

  代码：

  for(register int i=1;i<=n;++i){
  for(register int j=1;j>=m;++j){//这里正好是与01背包相反
        if(j>=w[i])f[j]=Min(f[j-v[i]]+w[i],f[j]);
    }
  }

• 多重背包：每种物品有若干个。

  显然可以将每种拆分成一个一个的，然后就变成了01背包。

  二进制优化：将每种物品按二进制拆分，跑01背包。因为所有数都可以二进制表示。

• 分组背包：物品分为若干组，每组只能选一个。

  就可以多一重循环，枚举每一组，再从组中枚举每一个。

• 有依赖的背包：每个物品可能需要先选别一个的物品再选它。

  那么依赖关系形成树形。则可以设\large f_i为选定i节点为根的子树能得到的最大价值，那么我们可以枚举每一个它的子树的体积求解。

  注意：\large f_i的含义是选定以i为根的子树能得到的最大价值，必须要选i节点。

区间dp

每次合并的是一个区间，例：NOI1995石子合并

代码：

for(register int i=2;i<=n;++i){//枚举区间大小
    for(register int l=1;l<=len-i+1;++l){//枚举区间左端点
        int r=l+i-1;
        for(register int k=l;k<r;++k){//枚举中间合并节点
            f[l][r]=Max(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);//sum为前缀和数组
        }
    }
}

树形dp

利用树的节点关系进行dp。比较适合进行记忆化搜索。

DAGdp

在DAG上dp，常用拓扑排序实现。

期望dp

常用求解法是设状态时，表示为差若干步到终点，而不是从起点过多少步。

顾名思义，求解期望的dp，常与DAG、树等联系起来，或是进行数学推导。

例：Cnoi2020线形生物

设 S_k为从1到k的期望步数。T_k为k的返祖边集合。

则有：

等号两边同乘\large |T_{k-1}|+1再移项得：

代码：

struct edge{//建图
    int end,nxt;
}e[1000010];
int head[1000010],cnt=0,tm[1000010];
ll s[1000010];
void adde(int x,int y){
    e[++cnt].end=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
    ++tm[x];
}

int main(){
    int id=qread(),n=qread(),m=qread();
    for(re int i=1;i<=m;++i){
        int x=qread(),y=qread();
        adde(x,y);
    }
    s[1]=0;
    for(re int i=2;i<=n+1;++i){//求解
        s[i]=((tm[i-1]+1)*(s[i-1]+1))%mod;
        for(re int j=head[i-1];j;j=e[j].nxt){
            s[i]=((s[i]-s[e[j].end])%mod+mod)%mod;
        }
        s[i]%=mod;
    }
    cout<<s[n+1]<<'\n';
    return 0;
}

状态压缩dp

当dp的某一组维度状态数都很小的时候就可以压成一个维度。称之为状态压缩。

实际上，状压在搜索中也有应用。

经典例题模型：二维平面放置物品，每个物品对于其他物品有限制，一维比较短，就可以将这一维压成一个数。

如：SCOI2005互不侵犯

可以将每一行压成一个二进制数，每一个二进制位的0/1代表这一格上有无国王。然后再考虑可行情况，枚举每一列求解即可。

代码：

int num[1<<9],s[1<<9],cnt=0;
ll a[20][201][1<<9];//a[i][k][j]表示前i行有k个国王当前行状态为j时的方案数
int main(){
    int n=qread(),m=qread();
    for(re int i=0;i<(1<<n);++i){
        if(i&(i<<1)) continue;
        int sum=0;
        for(re int j=0;j<n;++j)
            if(i&(1<<j)) sum++;
        num[++cnt]=sum;
        s[cnt]=i;
    }
    a[0][0][1]=1;
    for(re int i=1;i<=n;++i)
        for(re int j=1;j<=cnt;++j)
            for(re int k=0;k<=m;++k)
                if(k>=num[j])
                    for(re int l=1;l<=cnt;++l)
                        if(!(s[j]&s[l]||(s[j]<<1)&s[l]||(s[j]>>1)&s[l]))
                            a[i][k][j]+=a[i-1][k-num[j]][l];
    ll ans=0;
    for(re int i=1;i<=cnt;++i){
        ans+=a[n][m][i];
    }
    cout<<ans<<'\n';
    return 0;
}

插头dp

将路径覆盖类似问题转化为状态压缩的dp技巧。

数位dp

与数有关的dp，一位一位考虑，n 位数就从一些 n-1 位数推过来。

注意数的范围。

dp优化

• 优先队列优化：使用优先队列（堆）进行的优化，枚举状态-->取较优状态。
• 单调队列优化:如果解a比解b优，且a出现的时候b在，则此时b就一定不会选择。（如果一个人比你小还比你强，你就该退役了）
• 斜率优化：特定题目使用，方便模板化的优化方式，直接减一维。

  图论

建图相关详情数据结构部分。

图的遍历

dfs：dfs序

bfs：拓扑序

欧拉路

并查集

查询合并的算法，适用范围很广，实现方法本质是连边建树。

• 优化：路径压缩（见代码）

初始化f[x]=x;

代码：

int ff(int x){//核心
    return x==f[x]?x:f[x]=ff(f[x]);
}
void add(int x,int y){//合并
    f[ff(x)]=ff(y);
}
int check(int x,int y){//查询
    return ff(x)==ff(y);
}

最短路

• Floyd算法求全源最短路

  适合于任何情况，就是时间复杂度较高。代码简单，能求很多东西，有很多变形。

  代码：

  for(re int k=1;k<=n;++k){
    for(re int i=1;i<=n;++i){
        if(k==i) continue;
        for(re int j=1;j<=n;++j){
            if(k==j||i==j) continue;
            f[i][j]=Min(f[i][j],f[i][k]+f[k][j]);
        }
    }
  }

  • Floyd求传递闭包：

  相连两边为1，不相连为0跑floyd，即求出传递闭包。

• dijkstra算法求单源最短路(只能跑正权图)

  本质为贪心。枚举每个目前能到达的点的出边松弛。复杂度

  • 堆优化：用堆维护当前最短路最短的松弛点。

  代码：

  memset(dis,0x3f,sizeof dis);
  dis[s]=0;
  q.push(make_pair(0,s));
  while(!q.empty()){
  int u=q.top().second;q.pop();
  if(vis[u]) continue;
  vis[u]=1;
  for(re int i=head[u];i;i=e[i].nxt){
      int v=e[i].end;
      if(dis[v]>dis[u]+e[i].value){
          dis[v]=dis[u]+e[i].value;
          q.push(make_pair(dis[v],v));
      }
  }
  }

• Bellman-Ford算法求单源最短路（可跑负权）

  枚举每个点，对于每个点，枚举每条边进行松弛操作。

  • 队列优化：SPFA 它死了

  从队列里取点，枚举出边，如果松弛成功，将终点加入队列。

  由于可以反复入队出队，它的复杂度很容易被卡。（但还是可以跑负权以及判负环的）

  代码：

  memset(dis,0x3f,sizeof dis);
  dis[s]=0;
  q.push(s);
  while(!q.empty()){
  int u=q.front;q.pop();
  inq[u]=0;
  for(re int i=head[u];i;i=e[i].nxt){
      int v=e[i].end;
      if(dis[v]>dis[u]+e[i].value){
          dis[v]=dis[u]+e[i].value;
          if(!inq[v])q.push(v),inq[v]=1;
      }
  }
  }

  • 判负环：如果一个点被入队了n次以上，就说明有负环。

• Johnson算法求全源最短路

tarjan算法

一类算法的总称，用dfs实现，引入时间戳概念。

• tarjan缩点

  核心思路：dfn数组是时间戳，low数组是回溯值，即能到达的最早时间戳。用孩子的low更新自己的low，并将扫到的点都加入栈中，如果更新完成后low==dfn（即自己就是自己能到达的最小时间戳），就将栈弹出到这个点，记为一个强联通分量。

  代码：

  void tarjan(int x){
    dfn[x]=low[x]=++dfsn;
    st[++top]=x;//入栈
    ins[x]=1;//标记入栈
    for(re int i=head[x];i;i=e[i].nxt){
        int v=e[i].end;
        if(!dfn[v]){
            tarjan(v);
            low[x]=Min(low[x],low[v]);
        }else if(ins[v]) low[x]=Min(low[x],low[v]);
    }
    if(low[x]==dfn[x]){
        cn++;//缩点后下标
        while(st[top]!=x){
            clr[st[top]]=cn;//标记缩点后下标
            ins[st[top]]=0;//出栈
            top--;
        }
        clr[x]=cn;//标记x
        ins[x]=0;
        top--;
    }
  }

• tarjan求割点

  同样也是有dfn和low数组，但low数组记录的是它出边能到达的节点中时间戳最小的。同时我们记录fa数组为它的根节点，一个点的fa就等于它父亲的fa。那么满足一下两种条件其一的即为割点：

  • fa为本身且这个点儿子数\le 2
  • 这个点儿子的low\gedfn且这个点不是根

  代码：

  void tarjan(int x){
    dfn[x]=low[x]=++dfsn;
    int kid=0;
    for(re int i=head[x];i;i=e[i].nxt){
        int v=e[i].end;
        if(!dfn[v]){
            fa[v]=fa[x];
            tarjan(v);
            low[x]=Min(low[x],low[v]);
            if(low[v]>=dfn[x]&&x!=fa[x]) cut[x]=1;
            if(x==fa[x]) kid++;
        }
        low[x]=Min(low[x],dfn[v]);
    }
    if(kid>=2&&x==fa[x]) cut[x]=1;
  }

二分图最大匹配

二分图：两个点集，同一集合间没有边，不同集合有边相连。

二分图最大匹配：将左边的点按边匹配右边的点，求最大匹配数。

• 匈牙利算法

  步骤：

  1. 对于每一个左点，沿边匹配右点
  2. 右点之前没有匹配过就匹配它；如果匹配过，就找它原匹配的左点（goto1）

  显然拿递归求解，每次递归右边的点只访问一次，时间复杂度O(nm)。

  小trick：时间复杂度与右点数无关，如果左点数比右点数多，可以尝试换一下左右节点。

  代码：

  bool dfs(int x){
    for(re int i=head[x];i;i=e[i].nxt){
        int v=e[i].end;
        if(!vis[v]){//每次dfs之前要初始化vis数组
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=x;
                return true;
            }
        }
    }
    return false;
  }

• 最大流求解

  可以建一个虚拟源点，连所有左点，建一个虚拟汇点，连所有右点，所有边权值均为1，然后跑最大流，结果即为最大匹配数。（不会证）

  速度快，但代码长，代码详见网络流部分。

网络流

不想打了，也不太会。

树论

其实也算图论，但分出来排版舒服。

树的直径

指树上最长一条链。可以dfs求。

树的重心

指距离其他点距离和最小的点。

最近公共祖先（lca）

• 树上倍增求lca

  利用 f 数组表示一个点的2的若干次方祖先，可以用dfs预处理出。

  求两个点的lca就尽量往上跳，但不能重合，最后不能跳了，它们此时的父亲就是原来两点的lca。

  代码：

  int dp[100010],f[100010][21],lg[100010];//dp表示深度，lg是对下标取log2后结果
  void dfs(int x,int fa){
    dp[x]=dp[fa]+1;
    f[x][0]=fa;
    for(re int i=1;(1<<i)<=dp[x];++i){
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(re int i=head[x];i;i=e[i].nxt){
        int v=e[i].end;
        if(v==fa) continue;
        dfs(v,x);
    }
  }
  int lca(int x,int y){
    if(dp[x]<dp[y]) swap(x,y);
    while(dp[x]>dp[y]) x=f[x][lg[dp[x]-dp[y]]-1];
    if(x==y) return x;
    for(re int i=lg[x]-1;i>=0;--i){
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    return f[x][0];
  }

• tarjan求lca

  离线算法，利用并查集维护祖先节点，dfs求解。

  每次访问一个节点，把它的祖先设为自己，查找子节点，让子节点的祖先指向自己，全部查找完毕后，打上vis标记并查询有没有与该节点相关的询问，如果有，分两种情况：

  • 另一端未访问，这时直接跳过。
  • 另一端访问过，这时另一端的祖先节点就是答案。

  对于询问的建立类似于链式前向星。

  代码：

  void tarjan(int x,int fa){
    f[x]=x;
    for(re int i=head[x];i;i=e[i].nxt){
        int v=e[i].end;
      if(v==fa) continue;
        tarjan(v,x);
      add(v,x);
    }
    vis[x]=1;
    for(re int i=hehe[x];i;i=q[i].nxt){
        int v=q[i].end;
        if(!vis[v]) continue;
        lca[i/2]=ff(v);
    }
  }

• 树链剖分求lca（不会）

• 欧拉+rmq求lca

最小生成树

• kruskal算法

  略

• prim算法

  不会

树链剖分

字符串算法

字符串哈希

将每一位字符当做一个27进制数位（或更高），求出一个大数再对大质数取模，得到结果即为这个字符串所对应的哈希值。

可能会重复出错，所以可以进行双哈希之类的操作。

Trie树

实际为数据结构，但因为字符串算法较为独立，分在这里。

KMP算法

字符串匹配算法。在一个字符串上匹配一个字符串。

manacher算法

寻找回文串算法。

AC自动机

可自动AC的算法

字符串匹配算法，在一个字符串上匹配多个字符串。

二、数据结构

栈

基础数据结构，先进后出。

单调栈

栈中元素单调。解决最优问题。

队列

基础数据结构，先进先出。

单调队列

队中元素单调。常用来解决滑动窗口、区间最优问题。

优先队列（堆）

实际是堆，常使用STL的priority_queue，见STL部分。

前缀和

区间查询数据结构，修改复杂度O(n)所以一般不修改。

递推实现：\large sum_i=sum_{i-1}+a_i，则查询l-r区间和即为\large sum_r-sum_{l-1}。

查询复杂度：O(1)

差分

区间修改单点查询数据结构，差分数组\large d_i=a_i-a_{i-1}。

将l-r位置的值加上x，只需要\large d_l+x，\large d_{r+1}-x就行了。复杂度O(1)

实际上前缀和和差分的修改和查询复杂度都不是均摊的，这就引出了下面的数据结构。

树状数组

单点修改区间查询数据结构，满足区间可减性题目可用，常数小，代码短。

修改：O(\log n)

查询：O(\log n)

可以利用差分变成单点查询区间修改。

代码：

int lwbit(int x){//求一个数二进制中最右边的1的值，核心代码。
    return x&(~x+1);
}
void update(int p,int x){//将p位置加上x
    while(p<=n){
        t[p]+=x;
        p+=lwbit(p);
    }
}
int srch(int p){//查询到p的前缀
    int sum=0;
    while(p>0){
        sum+=t[p];
        p-=lwbit(p);
    }
    return sum;
}
//求l到r区间即求srch(r)-srch(l-1)

线段树

支持多种操作的强大数据结构，修改和查询均为O(\log n)但常数较大，代码较长。一般递归实现。

一般为单点修改区间查询，可以利用差分变成单点查询区间修改。

具体而言，实现的功能取决于存储什么量和下放。

• 优化：lazytag用来减少递归次数。而这就牵扯到lazytag的相互干扰，在下放和修改时要格外注意。

模板（以加乘为例）：

#define ls p<<1
#define rs p<<1|1
//宏定义，加大可读性
struct Tree{
    int val;//值
    int lta,ltm；//lazytag
}t[100010<<2];//注意要开4倍空间
void pushup(int p){//上放
    t[p].val=t[ls].val+t[rs].val;
}
void pushdown(int u,int v,int p){//下放，重点
    t[ls].ltm*=t[p].ltm;
    t[rs].ltm*=t[p].ltm;
    t[ls].lta*=t[p].ltm;
    t[rs].lta*=t[p].ltm;
    t[ls].val*=t[p].ltm;
    t[rs].val*=t[p].ltm;
    t[p].ltm=1;
    int mid=(u+v)>>1;
    t[ls].val+=(mid-u+1)*t[p].lta;
    t[rs].val+=(v-mid)*t[p].lta;
    t[ls].lta+=t[p].lta;
    t[rs].lta+=t[p].lta;
    t[p].lta=0;
}
void build(int u,int v,int p){//建树
    t[p].ltm=1;
    if(u==v){
        t[p].val=a[u];
        return;
    }
    int mid=(u+v)>>1;
    build(u,mid,ls);
    build(mid+1,v,rs);
    pushup(p);
}
void upda(int l,int r,int u,int v,int p,int x){//加
    if(l<=u&&r>=v){
        t[p].val+=(v-u+1)*x;
        t[p].lta+=x;
        return;
    }
    int mid=(u+v)>>1;
    pushdown(u,v,p);
    if(l<=mid) upda(l,r,u,mid,ls,x);
    if(r>mid) upda(l,r,mid+1,v,rs,x);
    pushup(p);
}
void updm(int l,int r,int u,int v,int p,int x){//乘
    if(l<=u&&r>=v){
        t[p].val*=x;
        t[p].lta*=x;
        t[p].ltm*=x;
        return;
    }
    int mid=(u+v)>>1;
    pushdown(u,v,p);
    if(l<=mid) updm(l,r,u,mid,ls,x);
    if(r>mid) updm(l,r,mid+1,v,rs,x);
    pushup(p);
}
int srch(int l,int r,int u,int v,int p){//查询
    if(l<=u&&r>=v){
        return t[p].val;
    }
    int mid=(u+v)>>1;
    int ans=0;
    pushdown(u,v,p);
    if(l<=mid) ans+=srch(l,r,u,mid,ls);
    if(r>mid) ans+=srch(l,r,mid+1,v,rs);
    return ans;
}

建图法

邻接矩阵

常用于floyd。

链式前向星

最常用。

ST表

倍增思想的应用。只能求区间最值等可重区间的量的数据结构。

完全可以被线段树代替，但是代码短。

代码：

平衡树

分为两大类（基本上）：splay和treap

splay

常用双旋splay，长，但能维护的东西多，是Link-Cut Tree 的基础。

treap

代码相对短，同时满足二分查找树和堆的性质。

非旋 treap（fhq treap） 代码短，挺好学的，将旋转操作改为使用分裂与合并解决。

STL

c++大杀器。

一般使用STL时都会使用已经封装好的数据类型。

sort

用法：sort(.begin,.end,比较函数)

快排，速度很快。

nth_element

用法 ：nth_element(开始位置，目标位置，结束位置后一个，比较函数)

将结束位置到开始位置排列后在目标位置的元素放到目标位置，复杂度O(n)。

priority_queue

实际上是堆，但是比一般手打堆快。（内部是红黑树）

默认是大根堆。改成小根堆：priority_queue<type,vector<type>,greater<type> >q;

成员函数：

• push(x) 添加数x

• pop() 弹出堆根

• empty() 返回是否为空

• size() 返回大小

map

支持c++14后，可以直接使用unordered_map，常数很小，基本等于O(1)。但空间占用大，头文件：unordered_map。

映射，map<type,type>。常数大，但方便使用。

可以直接用类似数组的方法访问。

成员函数：

• insert(pair<type,type>(x,y)) 添加元素
• find(x)查询元素地址
• clear()清空
• count(x)x出现几次
• size()返回大小
• empty()返回是否为空
• begin()返回最初元素位置
• end()返回最后元素后一个位置

set/multiset

也可使用unordered_set

只保存关键字，集合，有序存储。

set去重，multset不去重。

• find()查询元素地址
• insert()添加
• erase()删除
• clear()清空
• count(x)x出现几次
• size()返回大小
• empty()返回是否为空
• begin()返回最初元素位置
• end()返回最后元素后一个位置

pair

两个量组成的数据单位。

pair<type,type> name定义。

成员变量：

• first第一个值
• second第二个值

pair先按第一个值排序，再按第二个值排序。

bitset

卡空间的神。还支持位运算。

直接当一个二进制数或只有0/1的数组使就行。

三、数学

主要偏向数论、组合、线性代数。

数论

经常出结论题，一般只有100分和50分暴力两档。

只讨论整数。

整除与同余

• \large a|b,b|c\Rightarrow a|c
• \large a\equiv b\pmod m\Rightarrow a\pm c\equiv b\pm c\pmod m\Rightarrow a\times c\equiv b\times c\pmod m
• \large a\mod m=a-\lfloor\frac{a}{m}\rfloor \times m
• 费马小定理：\large a^{p-1}\equiv 1\pmod p \large p为质数
• 欧拉定理：\large a^{\varphi(p)}\equiv 1\pmod p \large \varphi(p) 为小于等于 \large p 且与 \large p 互质的数个数，为积性函数。
• 扩展欧拉定理：\large a^b\equiv a^{b\mod\varphi(p)+\varphi(p)}\pmod p

快速幂

ll qpow(ll x,int k){
    ll sum=1;
    while(k){
        if(k&1) sum*=x;
        x*=x;
        k>>1;
    }
    return sum;
}

• 矩阵快速幂：将以上乘法变成矩阵乘法。

质数（素数）

• 定义：只有两个因数的数。

• 唯一分解定理（算术基本定理）：一个数能分解成若干质数的若干次幂乘积形式且有唯一分解形式。

• 线性筛素数：

  for(re int i=2;i<=n;++i){
    if(!np[i]) p[++cnt]=i;
    for(re int j=1;j<=cnt&&p[j]*i<=n;++j){
        np[i*p[j]]=1;
        if(i%p[j]==0) break;
    }
  }

  线性筛欧拉函数 \varphi 与其很像：

  for(re int i=2;i<=n;++i){
    if(!phi[i]) p[++cnt]=i,phi[i]=i-1;
    for(re int j=1;j<=cnt&&p[j]*i<=n;++j){
        phi[i*p[j]]=phi[i]*(p[j]-1);
        if(i%p[j]==0){
            phi[i*p[j]]=phi[i]*p[j];
          break;
        }
    }
  }

最大公约数（gcd）和最小公倍数（lcm）

• 欧几里得算法（辗转相除法）：

  int gcd(int a,int b){//尽量保证a>b
    if(b==0) return a;
    return gcd(b,a%b);
  }

• 互质：(a,b)=1

• 求lcm：\large [a,b]=\frac{a\times b}{(a,b)}

• 裴蜀定理：对于整数 a,b，有方程 \large ax+by=(a,b) 一定有整数解。特别的，如果 a,b 互质，ax+by=1 一定有整数解。

这就引出了：

• 扩展欧几里得算法： 考虑方程 \large ax+by=(a,b) 当 \large b=0 时，有 \large (a,b)=a（即欧几里得算法的解）。

  此时：\large\left\{ \begin{array}{l} x=1 \\ y=0 \end{array} \right.

  当\large b \ne 0时，利用欧几里得算法递归求解：

  \begin{array}{l} a'=b \\ b'=a \% b \end{array} \right.

  此时\large (a,b)=(a',b')

  设方程\large a'x+b'y=(a',b')=(a,b)解为\large x',y'则有：

  \large a'x'+b'y'=(a,b)\Rightarrow bx'+(a\% b)y'=(a,b)

  由于 \large a\% b=a-\lfloor\frac{a}{b}\rfloor\times b，有：

  \large bx'+ay'-b\times\lfloor\frac{a}{b}\rfloor y'=(a,b)

  变形一下：

  \large ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')=(a,b)

  则原方程的解：\large\left\{ \begin{array}{l} x=y' \\ y=x'-\lfloor\frac{a}{b}\rfloor y' \end{array} \right.

  即可递归求解。代码：

  void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
    return;
  }

逆元

• 定义：对于整数 \large a,b，有 \large ab\equiv1\pmod p 则称 \large a,b 互为逆元。

• OI中大部分模数为质数，由费马小定理：\Large \frac{1}{a} \large \equiv a^{p-2} \pmod p，可以用快速幂求解。

组合计数

前置知识

1. 阶乘（\large!）：\large n!=n\cdot (n-1)\cdot(n-2)\cdots2\cdot1

排列数和组合数

• 定义：\Large A_n^m为从n个物品中选m个排列，\Large A_n^m=\frac{n!}{(n-m)!}

  \Large C_n^m$为从$n$个物品中选 $m$ 个组合，$\Large C_n^m=\frac{n!}{m!(n-m)!}$，又记做$\Large \binom{n}{m}

• 一般阶乘数都很大，所以大部分情况求解取模。

• 由于涉及除法，要进行求逆元。可以用 \large O(n) 时间复杂度求出 \large 1! 到 \large n! 的阶乘的逆元:

  \Large \frac{1}{(n-1)!}=\frac{n}{n!}\Rightarrow\frac{1}{(n-1)!}\equiv inv(n!)\times n\pmod p

• 卢卡斯定理：用于模数小，n,m 大的情况。

  \Large \binom{n}{m}\equiv \Large \binom{\frac{n}{p}}{\frac{m}{p}}\times\Large\binom{n\mod p}{m \mod p}\pmod p