note-未完成

2024-01-29 08:47:52

约定 _xxx() 表示有 xxx 功能的函数且仅表意思不代表具体函数

所有算法用伪代码描述

大概来说所有的变量类型都是可以变动的书写的仅是比较常用的类型

笔记部分口胡不保证完全正确

~~大部分都是数学~~

图论

生成树

稠密图上 $\mathrm{Prim}$ 优稀疏图上 $\mathrm{Kruskal}$ 优

Kruskal

复杂度 $O(n \log n)$

struct Edge{int from,to,dis;}e[MAX<<1]; //这里存图比较特殊
int f[MAX];
//
void addedge(int from,int to,int dis) {e[++cnt]=(Edge){from,to,dis};} //特殊的加边
//并查集
void union(int x,int y);
int find(int x);
//
int Kruskal()
{
    int re=0,tot=0;
    for(int i=1;i<=MAX;i++) f[i]=i;
    sort(e+1,e+num_edge+1,_cmpDis());
    for(int i=1;i<=num_edge;i++)
    {
    	int u=find(e[i].from),v=find(e[i].to);
        if(u==v) continue;
        tot+=1; re+=e[i].dis;
    	f[u]=v;
        if(tot==n-1) break;
    }
    return re;
}

Prim

复杂度 $O(n \log n)$

struct Edge{int next,to,dis;}e[N<<1];
int head[N],cnt,vis[N],dis[N];
_set(allVar,0);
//
void addege(int from,int to,int dis); //加边
//
int prim()
{
	int s=_rand(inV),tot=0,re=0,u=s;
    _set(dis,_minusINF()); dis[s]=0;
    for(int i=head[s];i;i=e[i].next) dis[e[i].to]=_cmp(dis[e[i].to],e[i].dis);
    while((++tot)<n)
    {
    	int m=_minusINF(); vis[u]=1;
        for(int i=1;i<=n;i++)
            if(!vis[i]&&_cmp(m,dis[i])) m=dis[i],u=i;
        re+=m;
        for(int i=head[u];i;i=e[i].next)
        {
        	int v=e[i].to;
            if(_cmp(dis[v],e[i].dis)&&!vis[v]) dis[v]=e[i].dis;
        }
    }
    return re;
}

重链剖分

建立复杂度 $O(n)$

int size[MAX],dep[MAX],fa[MAX],top[MAX],dfn[MAX],rnk[MAX],idx;
struct Edge{int next,to,dis;}e[MAX<<1];
_set(allVar,0);
//
void dfs1(int u,int f)
{
	size[u]=1; dep[u]=dep[f]+1; fa[u]=f;
    for(int i=head[u];i;i=e[i].next)
    {
    	int v=e[i].to;
        if(v==f) continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[son[u]]<size[v]) son[u]=v;
    }
}
void dfs2(int u,int topf)
{
    top[u]=topf; dfn[u]=++idx; rnk[idx]=u;
    if(!son[u]) return ;
    dfs2(son[u],topf);
    for(int i=head[u];i;i=e[i].next)
    {
    	int v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

最近公共祖先(LCA)

树链剖分

单次查询复杂度 $O(\log n)$

跳链时每次跳深度大的点

int size[MAX],dep[MAX],fa[MAX],top[MAX],dfn[MAX],rnk[MAX],idx;
struct Edge{int next,to,dis;}e[MAX<<1];
_set(allVar,0);
//
void addedge(int from,int to,int dis); //加边
//重链剖分
void dfs1(int u,int f); 
void dfs2(int u,int topf);
//
int lca(int x,int y)
{
	while(top[x]!=top[y])
    {
    	if(dep[top[x]]>=dep[top[y]]) x=fa[top[x]];
        else y=fa[top[y]];
    }
    return dep[x]<dep[y]?x:y;
}

倍增

建立复杂度 $O(n \log n)$

单次查询复杂度 $O(\log n)$

int log2[MAX],dep[MAX],fa[MAX][log2[MAX]];
struct Edge{int next,to,dis;}e[MAX<<1];
//
void addedge(int from,int to,int dis); //加边
//开始前运行
getLog2();
perDfs(root,0);
//
void getLog2()
{
	log2[0]=-1;
    for(int i=1;i<=MAX;i++) log2[i]=log2[i>>1]+1;
}
void preDfs(int u,int f)
{
	dep[u]=dep[f]+1;
    fa[u][0]=f;
    for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=e[i].next)
		if(e[i].to!=f) preDfs(e[i].to,u);
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=fa[x][log2[dep[x]-dep[y]]];
    if(x==y) return x;
    for(int i=log2[dep[x]];i;i--)
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

最短路

Dijkstra

复杂度稳定的 $O((v+e) \log v)$

#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
//
int dis[MAX],vis[MAX];
struct Edge{int next,to,dis;}e[MAX<<1];
//
void addedge(int from,int to,int dis); //加边
//
void Dijkstra(int S,int T)
{
    _set(dis,INF); _set(vis,0);
    priority_queue<pii,vector<pii>,greater<pii> > q;
    q.push(mp(0,S)); dis[S]=0;
    while(!q.empty())
    {
    	int u=q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        {
        	int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis)
            {
            	dis[v]=dis[u]+e[i].dis;
                if(!vis[v]) q.push(mp(dis[v],v));
            }
        }
    }
    return dis[T];
}

SPFA

大部分复杂度 $O(kn)$ 最坏 $O(nm)$

在分层图上跑的飞飞飞飞快

int dis[MAX],vis[MAX];
struct Edge{int next,to,dis;}e[MAX<<1];
//
void addedge(int from,int to,int dis); //加边
//
void SPFA(int S,int T)
{
    _set(dis,INF); _set(vis,0);
    queue<int> q;
    q.push(S); dis[S]=0; vis[S]=1;
    while(!q.empty())
    {
    	int u=q.front(); q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
        	int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis)
            {
            	dis[v]=dis[u]+e[i].dis;
                if(vis[v]==0) vis[v]=1,q.push(v);
            }
        }
    }
}

Floyd

复杂度 $O(n^3)$

int e[MAX][MAX];
//
_set(e,INF);
_set(e[u][v],min(dis[u][v]));
void Floyd()
{
	for(int k=1;k<=MAX;k++)
		for(int i=1;i<=MAX;i++)
            for(int j=1;j<=MAX;j++) e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
}

Johnson

全源最短路复杂度 $O(nm \log m)$

新建一个超级源点 $S$ ,从其向所有点连一条边权为 $0$ 的边

用队列优化的 $Bellman-Ford$ 算法求出 $0$ 号点到其它所有点的最短路

对于一条 $u \to v$ 边权为 $w$ 的边,将边权重新设为 $w+h_i-h_v$

再以每个点为起点求出任意两点之间的最短路

int dis[MAX],vis[MAX],h[MAX];
struct Edge{int next,to,dis;}e[MAX<<1];
//
void addedge(int from,int to,int dis);
bool SPFA(int S); //普通的SPFA+判负环 true/false表是否有负环
void Dijkstra(int S);
//
void Johnson()
{
	_getGap();
    int S=_nonGapV(); //S=0
    for(int i=1;i<=MAX;i++) addedge(S,i,0);
    if(SPFA(S)) //SPFA跑出来的最短路记为 h[MAX]
    {
    	_getNegativeCircle();
        return ;
    }
	for(int u=1;u<=n;u++)
       	for(int i=head[u];i;i=e[i].next)
        {
        	int v=e[i].to;
            e[i].w=h[u]-h[v];
        }
    for(int i=1;i<=n;i++) Dijkstra(i);为
}

网络流

Dinic

数据结构

并查集

如果加了按秩合并+路径压缩单次修改查询复杂度 $O(\alpha(n))$

只有路径压缩单次修改查询复杂度 $O( \log n)$

按秩合并策略:将小的树连到大的树上

int f[MAX],size[MAX];
_set(f[i],i); _set(size[i],0)
//
void union(int x,int y) //按秩合并
{
	int fx=query(x),fy=query(y);
    if(fx==fy) return ;
    if(size[fx]>size[fy]) swap(fx,fy);
    f[fx]=fy; size[fy]+=size[fx];
}
int query(int x) //路径压缩
{
	return f[x]==x?x:f[x]=query(f[x]);
}

堆

STL

priority_queue<T,vector<T>,greater<T> > ;
priority_queue<T,vector<T>,less<T> > ;

手写

struct Heap{
	int h[MAX],size;
    void init() {_set(h,size,0);} 
	void push(int v)
    {
        int now=v;
    	h[++size]=v;
    	while(now)
        {
        	int next=now>>1;
            if(_cmp(h[next],h[now])) swap(h[next],h[now]);
            else break;
            now=next;
        }
    }
    void top() {return h[1];}
    void pop()
    {
    	swap(h[1],h[size--]);
        int now=1;
        while((now<<1)<=size)
        {
        	int next=now<<1;
            if(next+1<=size&&_cmp(h[next+1],h[next])) next++;
            if(_cmp(h[next,h[now]])) swap(h[next],h[now]);
            else break;
            now=next;
        }
    }
};

树状数组

单次修改查询复杂度 $O(\log n)$

常数小跑得比线段数快

单修区查

struct BitTree{
	int t[MAX],n;
    void init() {_set(t,_need());}
    int lowbit(int x) {return x&(-x)};
    void modify(int x,int k) {while(x<=n) t[x]=_update(t[x],k),x+=lowbit(x);}
	int query(int x)
    {
    	int re=0;
        while(x) re=_update(re,t[x]),x-=lowbit(x);
        return re;
    }
};

区修单查

struct BitTree{
	int s[MAX],delta[MAX],n;
    void init() {_set(delta,_need()); _set(s);}
    void modify(int x,int k) {while(x<=n) delta[x]=_update(delta[x],k),x+=lowbit(x);}
    void modify(int l,int r,int k) {modify(l,k); modify(r+1,_invOperation(k));}
    int query(int x)
    {
    	return re=0;
        while(x) re=_update(re,delta[x]),x-=lowbit(x);
        return _update(re,s[x]);
    }
};

线段树

单次修改查询复杂度 $O(\log n)$

struct Sgtree{
    int init[MAX];
    struct node{int l,r,...;}t[MAX<<2];
    void init() {_set(init);}
    void update(int p) {_update_from_ltree_rtree();}
    void pushdown(int p) {_pushdown_to_ltree__rtree();}
    void build(int p,int l,int r)
    {
        t[p].l=l; t[p].r=r; _setnode();
    	if(l==r)
        {
            t[p]=_newnode(p);
        	return ;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid); build(p<<1|1,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int k)
    {
    	if(l<=t[p].l&&r>=t[p].r)
        {
        	_modifynode();
            return ;
        }
        pushdown(p);
        int mid=(t[p].r+t[p].l)>>1;
        if(l<=mid) modify(p<<1,l,mid);
        if(r>mid) modify(p<<1|1,mid+1,r);
        update(p);
    }
    int query(int p,int l,int r)
    {
    	if(l>=t[p].l&&r>=t[p].r) return _needVal();
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1,re=0;
        if(l<=mid) re=_update(re,query(p<<1,l,r));
        if(r>mid) re=_update(re,query(p<<1|1,l,r));
        return re;
    }
};

ST表

$O(n \log n)$ 建表 $O(1)$ 查询

int log2[MAX],st[MAX][log2[MAX]];
//
void preSolve()
{
	log2[0]=-1;
    for(int i=1;i<=MAX;i++) log2[i]=log2[i>>1]+1;
    for(int i=1;i<=MAX;i++) _get(st[i][0]); //每个点
	for(int j=1;j<=log2[MAX];j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=_cmp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
void RMQ(int l,int r)
{
	int t=log2[r-l+1];
    return max(st[l][t],st[r-(1<<t)+1][t]);
}

平衡树

Fhq-Treap

Splay

珂朵莉树

仅在数据随机的情况下复杂度为 $O(n \log n)$

大部分情况都是 $O(玄学)$

#define iter set<node>::iterator
//
struct node{
	int l,r; mutable int v;
    node(const int L,int R=-1,int V=0):l(L),r(R),v(V){}
    bool operator<(const node &x)const {return l<x.l;}
};
set<node> s;
//
iter split(int p)
{
	if(p>MAX) return s.end();
    iter i=--s.upper_bound(node(p));
    if(i->l==p) return i;
    int l=i->l,r=i->r,v=i->v;
    s.erase(i);
    return s.insert(node(l,p-1,v)),s.insert(node(p,r,v)).first;
}
void assign(int l,int r,int v)
{
	iter ir=split(r+1),il=split(l);
    s.erase(il,ir);
    s.insert(node(l,r,v));
}
int performance(int l,int r)
{
	iter ir=split(r+1),il=split(l);
    for(;il!=ir;++il)
    	_anything();
}

分块

一般的取块大小为 $\sqrt n$

int s[MAX],block[SIZE];
//
void build()
{
    _get(s);
	int size=_size(MAX);
    for(int i=1;i<=n;i++)
    {
    	id[i]=(i-1)/size+1;
        _update(block[id[i]],s[i]);
    }
}
int action(int l,int r,...)
{
	int lid=id[l],rid=id[r];
    if(lid==rid)
    {
    	for(int i=l;i<=r;i++) _solve(s[i],block[i]);
    	return _need();
    }
    for(int i=l;id[i]==lid;i++) _solve(s[i],block[i]);
    for(int i=lid+1;i<rid;i++) _solve(block[i]*size);
    for(int i=r;id[i]==rid;i--) _solve(s[i],block[i]);
    return _need();
}

数学

数学部分的代码部分还在咕咕中

快速幂

求解 $a^k\equiv c \mod p$ 中的 $c$

int qpow(int a,int k,int p) //a^k (mod p)
{
    int re=1;
	while(k)
    {
    	if(k&1) re*=a,re%=p;
        a*=a; a%=p;
        k>>=1;
    }
    return re;
}
//另一种写法
int qpow(int a,int b,int p)
{
	int re=1;
    for(;b;b>>=1,a=a*a%p)
        if(b&1) re=re*a%p;
    return re;
}

质数

素数分布定理

设 $\pi(x)$ 是不超过 $x$ 的素数的个数则 $\pi(x) \sim \dfrac{x}{\ln x}$

算术基本定理

任何一个大于 $1$ 的正整数都能有限分解为有限个质数的乘积即 $N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$

其中 $c_i$ 为正整数 $p_i$ 为质数且满足 $p_1<p_2<...<p_m$

算术基本定理的推论

有 $N$ 的正约束集合 $(p_1^{b_1}p_2^{b_2}...p_m^{b_m})$ 其中 $0\le b_i\le c_i$

有 $N$ 的正约数个数 $(c_1+1)\times (c_2+1)\times ... \times (c_m+1)=\prod\limits_{i=1}^{m}(c_i+1)$

有 $N$ 的所有正约数的和 $(1+p_1+...+p_1^{c_1})\times ... \times (1+p_m+...+p_m^{c_m})=\prod\limits_{i=1}^{m}(\sum\limits_{j=0}^{c_i}(p_i)^j)$

线性筛

int noPrime[i];
//
void getPrime()
{
    _set(noPrime,0);
	noPrime[0]=noPrime[1]=1;
    for(int i=2;i*i<=MAX;i++)
    	if(!noPrime[i]) for(int j=i+i;j<=MAX;j+=i) noPrime[j]=1;
}

同余

费马小定理

若 $p$ 为质数则对于任意整数 $a$ 有 $a^p \equiv a\mod p$

欧拉定理

若 $a,m$ 互质则 $a^{\varphi(m)}\equiv 1 \mod m$

扩展欧拉定理

\[a^b \equiv \left\{\begin{aligned} a^{b \mod \varphi(p)} \qquad gcd(a,p)=1 \\ a^b \qquad gcd(a,p)\ne1,b<\varphi(p)\\ a^{b\mod \varphi(p)+\varphi(p)} \qquad gcd(a,p)\ne1,b\ge \varphi(p) \end{aligned} \right. \mod p \]

逆元

线性求逆元

要求 $p$ 为质数

int inv[MAX];
//
void getInv()
{
    inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=(p-(p/i))*inv[p%i]%p;
}

拓展欧几里得求逆元

即求 $ax+py\equiv1 \mod p$ 的一组整数解

要求 $gcd(a,p)=1$

则 $x$ 为一个解所以 $a^{-1}=x$

exgcd(a,p,x,y);

费马小定理求逆元

有 $a^{p-1}\equiv 1 \mod p$ 要求 $p$ 为质数

所以 $a^{-1}=a^{p-2}$

invA=qpow(a,p-2,p);

最大公约数

最大公约数定理

有 $\forall a,b \in \N ,\qquad gcd(a,b)\times lcm(a,b)=a\times b$

有时也记 $(a,b)$ 为 $gcd(a,b)$ 记 $[a,b]$ 为 $lcm(a,b)$

有 $(a,b)[a,b]=ab$

辗转相除法

求 $gcd(x,y)=c$ 的 $c$

int gcd(int x,int y)
{
	return y==0?x:gcd(y,x%y);
}

位运算加速(有一定限制找不到了一般都没问题)

int gcd(int x,int y)
{
	while(y^=x^=y^=x%=y) ;
    return x;
}

拓展欧几里德算法

给出不定方程 $ax+by=gcd(a,b)$ 求出其一组特解

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

积性函数

若当 $a,b$ 互质有 $f(ab)=f(a)f(b)$ 则 $f$ 为积性函数

欧拉函数

定义 $\varphi(n)$ 即小于等于 $n$ 的与 $n$ 互相质的数的个数

性质:

$\varphi(1)=1$
当 $n$ 为质数 $\varphi(n)=n-1$
$\varphi(n)$ 是积性函数则若 $a,b$ 互质 $\varphi(ab)= \varphi(a)\varphi(b)$
$\forall n>1$ $1\sim n$ 中与 $n$ 互质的数的和为 $\frac{n\times \varphi(n)}{2}$

对于一个数 $n$ 有 $\varphi(n)=n\times \frac{p_1-1}{p_1}\times ...\times \frac{p_m-1}{p_m}=n\times \prod\limits_{p|n}(1-\frac{1}{p})$ 其中 $p$ 为质数

筛法

有 $\varphi(n)=\varphi(p)\times\varphi(n')=(p-1)\times\varphi(n')$

int phi[MAX];
//
void getPhi()
{
	_set(phi,0);
    phi[1]=1;
    for(int i=2;i<=n;i++)
        if(!phi[i])
            for(int j=i;j<=n;j+=i)
            {
            	if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}

线性基

给出一个集合 $A$ , 令 $c=c\ xor \ x_i \quad x_i \in A$ , 求最大的 $c$

long long A[MAX],bit[65],ans;
//
void getBit(int x)
{
	for(int i=62;i;i--)
    {
    	if(!(x>>(ll)i)) continue;
        if(!bit[i])
        {
            bit[i]=x;
            break;
        }
        x^=bit[i];
    }
}
int solve()
{
	for(int i=1;i<=MAX;i++) _get(A);
    for(int i=1;i<=MAX;i++) getBit(A[i]);
	ans=0;
    for(int i=62;i;i--)
        if((ans^bit[i])>ans) ans^=bit[i];
    return ans;
}

同余方程

线性同余方程

给出 $a,b,m$ 求一个整数 $x$ 满足 $ax \equiv b \mod m$

原式可转为 $ax+my=b$ 则有

$ax+my=b \iff a\frac{x_0b}{(a,m)}+b\frac{y_0b}{(a,m)}=b$ 当且仅当 $(a,m)|b$ 有整数解

则有一组特解 $x_0=x'\times \frac{b}{(a,m)},y_0=y'\times \frac{b}{(a,m)}$

有通解 $x=x_0+k\frac{m}{(a,m)},y=y_0+k\frac{a}{(a,m)} \quad k\in \Z$

中国剩余定理

设 $m_1,m_2,...,m_n$ 是两两互质的整数令 $m=\prod\limits_{i=1}^{n} m_i,M_i=m/m_i$ $t_i$ 是方程 $M_it_i \equiv 1 \mod m_i$ 的一个解

则对于任意的 $n$ 个整数 $a_1,a_2,...,a_n$ 方程组

\[\left\{\begin{aligned} x \equiv a_1 \mod m_1 \\ x \equiv a_2 \mod m_2 \\ \vdots \\ x \equiv a_n \mod m_n \end{aligned} \right. \]

有整数解为 $x=\sum\limits_{i=1}^{n} a_iM_it_i$

拓展中国剩余定理

给出数列 $a_1,a_2,...,a_n$ 和数列 $m_1,m_2,...,m_n$ 求一个最小正整数 $x$ 满足 $\forall i\in[i,n]$ 有 $x\equiv a_i \mod m_i$

或者判断无解与上不同的是 $m_i$ 不一定两两互质

考虑数学归纳法

假设已经求出了前 $k-1$ 个方程构成的方程组的解 $x$ 记 $m=\prod\limits_{i=1}^{k-1} m_i$ 则 $x+qm,q\in \Z$ 是方程的通解

考虑加入第 $k$ 个方程现要求求出一个整数 $t$ 使 $x+tm \equiv a_k \mod m_k$

该方程等价于求解 $tm \equiv a_k-x \mod k$ 的解 $t$

此时可求出解或判断有无解

新方程组的解即为 $x'=x+tm$

则反复使用 $n$ 次拓展欧几里得算法即可求解整个方程组

BSGS

给出 $b,p,n$ 求形如 $b^l =n \mod p$ 时 $l$ 的值

#define ll long long
//
ll qpow(ll a,ll k,ll p); //快速幂
//
ll BSGS(ll p,ll b,ll n)
{
    map<ll,ll> h;
    ll now=n%p;
	ll m=ceil(sqrt(p));
    for(int i=1;i<=m;i++)
    {
    	now*=b; now%=p;
        if(!h[now]) h[now]=i;
    }
    now=qpow(b,m,p);
    ll tmp=now;
    for(int i=1;i<=m;i++)
        if(h[now]) return (i*m-h[now]%p+p)%p;
    	else now*=tmp,now%=p;
    return -1;
}

矩阵

由 $n\times m$ 个数 $a_{i,j}$ 排成的 $m$ 行 $n$ 列的数表

\[\notag \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m_1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}_{m \times n} \quad \]

注:矩阵本身并不代表任何意义,甚至可以看作一个二维数组,但是,可以人为赋予意义或从多个角度看待矩阵

可以说矩阵是描述抽象事物的工具

特别的当 $n=m$ 时可以称为方阵当 $n=1$ 或 $m=1$ 时可以看作向量

如果一个矩阵的元素可以被一个只与行 $i$ 列 $j$ 有关的统一函数 $f$ 表示也可记为 $(f(i,j))_{m \times n}$

运算

一个 $n\times m$ 的矩阵可以看作 $n\times m$ 的二维数组

有三个矩阵 $A,B,C$ 有

加减法

$C=A \pm B \iff \forall i\in [1,n],\forall j\in[1,m],C_{i,j}=A_{i,j} \pm B_{i,j}$

即有

\[\notag \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix} \quad \pm \begin{pmatrix} b_{11} & \cdots & b_{1n} \\ \vdots & & \vdots \\ b_{m1} & \cdots & b_{mn} \end{pmatrix} \quad = \begin{pmatrix} a_{11} \pm b_{11} & \cdots & a_{1n}\pm b_{1n} \\ \vdots & & \vdots \\ a_{m1} \pm b_{m1} & \cdots & a_{mn} \pm b{mn} \end{pmatrix} \quad \]

乘法

数乘

$\lambda A \iff \forall i\in [1,n],\forall j\in[1,m],A_{i,j}=\lambda A_{i,j}$

即有

\[\notag \lambda \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix} \quad = \begin{pmatrix} \lambda a_{11} & \cdots & \lambda a_{1n} \\ \vdots & & \vdots \\ \lambda a_{m1} & \cdots & \lambda a_{mn} \end{pmatrix} \quad \]

矩阵相乘

设 $A$ 是 $n \times m$ 的矩阵 $B$ 为 $m \times p$ 的矩阵

则 $C=AB$ 是 $n\times p$ 的矩阵仅有 $A$ 的列数(行数)与 $B$ 的行数(列数)相等的时候才能求

$C=A B \iff \forall i\in [1,n],\forall j\in[1,p],C_{i,j}=\sum\limits_{k=1}^{m} (A_{i,k}\times B_{k,j})$

即有 $m \times p$ 的矩阵 $A$ 设其一行为 $A_i$ 有 $p \times n$ 的矩阵 $B$ 设其一列为 $B_i$ 则有

$m \times n$ 的矩阵 $C=AB$

\[\notag \begin{pmatrix} A_1 \\ A_2 \\ \vdots \\ A_m \end{pmatrix} \quad \begin{pmatrix} B_1,B_2,\cdots,B_n \end{pmatrix} \quad = \begin{pmatrix} A_1B_1 & \cdots & A_1B_n\\ \vdots & & \vdots \\ A_mB_1 & \cdots & A_mB_n \end{pmatrix} \quad \]

其中 $A_iB_j=\sum\limits_{k=1}^{p} a_{k}b_{k}矩阵$

这里用了矩阵分块法....矩阵是可以划分成子矩阵形成的矩阵的

性质

加减

$A+B=B+A$
$(A+B)+C=A+(B+C)$
$A+(-A)=O$
$A-B=A+(-B)$

数乘

$(\lambda \mu) A = \lambda (\mu A)$
$\lambda A+\lambda B=\lambda(A+B)$
$\lambda(A+B)=\lambda A+\lambda B$

乘

$(AB)C=A(BC)$
$\lambda (AB)=(\lambda A)B=A (\lambda B)$ 其中 $\lambda$ 为数
$A(B+C)=AB+AC,(B+C)A=BA+CA$
$EA=AE=A$
$A^kA^l=A^{k+l}$ $(A^k)^l=A^{kl}$

矩阵乘法不满足交换律有 $AB$ 不一定等于 $BA$

转置矩阵

对于一个矩阵 $A$ 交换其行与列,记为 $A^T$

即有

\[\notag \begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_m \end{pmatrix} ^T = \quad \begin{pmatrix} a_1,a_2,\cdots,a_n \end{pmatrix} \quad \]

性质

$(A^T)^T=A$
$(A+B)^T=A^T+B^T$
$(\lambda A)^T=\lambda A^T$
$(AB)^T=A^TB^T$

单位矩阵

主对角线为 $1$ 其余为 $0$ 的矩阵是一个 $n\times n$ 的方阵

可记为 $I$ $E$ $U$

有 $I_n=\mathrm{diag}(1,1,...,1)$

余子式

设一个 $n \times m$ 的矩阵 $A$

则 $A$ 的 $(i,j)$ 余子式 $M_{ij}$ 为 $A$ 去掉第 $i$ 行第 $j$ 列后得到的 $n-1$ 阶子矩阵的行列式

代数余子式

一个矩阵 $A$ 的代数余子式 $C_{ij}=(-1)^{i+j}M_{ij}$

伴随矩阵

将行列式 $|A|$ 的各元素的代数余子式 $A_{ij}$ 构成以下矩阵

\[\notag A^* = \begin{pmatrix} A_{11} & \cdots & A_{1n} \\ \vdots & & \vdots \\ A_{m1} & \cdots & A_{mn} \end{pmatrix} \quad \]

则 $A^*$ 为 $A$ 的伴随矩阵

有 $AA*=A^*A=|A|E$

逆矩阵

对于 $n$ 阶矩阵 $A$ 如果有一个 $n$ 阶矩阵 $B$ ,使 $AB=BA=E$

那么称矩阵 $A$ 是可逆的,称 $B$ 为 $A$ 的逆矩阵,记为 $A^{-1}$

性质

若 $A$ 可逆,则其逆矩阵唯一
若 $A$ 可逆,则 $|A| \ne 0$
若 $|A|\ne 0$ 则矩阵 $A$ 可逆,且 $A^{-1}=\dfrac{1}{|A|}A^*$
若 $AB=E$ 或 $BA=E$ 则 $B=A^{-1}$

运算规律

若 $A$ 可逆,则 $A^{-1}$ 也可逆,且 $(A^{-1})^{-1}=A$
若 $A$ 可逆,数 $\lambda \ne 0$ ,则 $\lambda A$ 可逆,且 $(\lambda A)^{-1}=\dfrac{1}{\lambda} A^{-1}$
若 $A,B $ 为同阶矩阵且均可逆,则 $AB$ 也可逆,且 $(AB)^{-1}=B^{-1}A^{-1}$

线性方程组

线性方程组为以下形式

\[\left\{\begin{aligned} a_{11}x_1+a_{12}x_2+\cdots +a_{1n}x_n=b_1 \\ \vdots \\ a_{m1}x_1+a_{m2}x_2+\cdots +a_{mn}x_n=b_m \end{aligned} \right. \]

可记为一个向量方程 $Ax=b$

其中有

\[\notag A= \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots && \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix} \quad , x=\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \quad , b= \begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix} \quad \]

线性变换

对于一个变换 $A$ 取两个向量,满足可加性和齐次性 有

\[\notag A(\alpha+\beta)=A \alpha+A \beta \\ A(k \alpha) =k A(\alpha) \]

则可以用矩阵描述这种变换

亦即 $f(x)=A_fx$

为 $\R^n$ 射到 $\R^m$ 的线性变换构成的向量空间 $\mathcal{L}(\R^n,\R^m)$ 上存在的一个到 $\mathcal{M}(m,n,\R)$ 的一一映射: $f \mapsto A_f$

图论

可以用一个矩阵 $E$ 描述一个有限图, $E$ 为相关矩阵的邻接矩阵,记录了图两顶点之间是否有边链接.对一个简单图而言,其元素取值为 $0/1$

一个距离矩阵 $E$ 各元素为点之间距离的矩阵

构造(转移)矩阵

考虑一种特殊的情况

设 $F$ 是一个 $1\times n$ 的矩阵(也就是数列) $A$ 是 $n \times n$ 的(转移)矩阵

有 $F,F'$ 为一维数组略去其行下标

对于 $\forall j \in [1,n]$ 有 $F'_j=\sum\limits_{k=1}^{n}(F_k \times A_{k,j})$

等价于在一个向量的 $k,j$ 两个状态之间发生了转移

这样可以用状态矩阵 $F$ 与一个转移矩阵 $A$ 来表示数列的线性递推关系

同时可以用矩阵快速幂优化这个过程总复杂度 $O(n^3 \log T)$

OI会用到的

矩阵加速递推

矩阵表达修改

定长路径统计

定长最短路

限长路径计数/最短路

struct Matrix //这份矩阵的正确性无法保证
{
    int e[MAX][MAX],n,m;
    Matrix E(int n);
    Matrix(int N=0,int M=0):n(N),m(M),e(){}
    Matrix operator+(const Matrix &x)const ;
    Matrix operator*(const Matrix &x)const ;
};

Matrix Matrix::I(int n)
{
    Matrix t=Matrix(n,n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) t.e[i][j]=1;
    return t;
}
Matrix Matrix::operator*(const Matrix &x)const
{
    Matrix t=Matrix(n,x.m);
    for(int k=1;k<=m;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=x.m;j++) t.e[i][j]+=e[i][k]*x.e[k][j];
    return t;
}
Matrix Matrix::operator+(const Matrix &x)const
{
    Matrix t=Matrix(n,m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) t.e[i][j]=e[i][j]+x.e[i][j];
    return t;
}
Matrix qpow(Matrix x,int k)
{
    Matrix e=e.I(x.n),t(x);
    while(k)
    {
        if(k&1) e=e*t;
        t=t*t; k>>=1;
    }
    return e;
}

行列式

在数学中,行列式是一个函数,其定义域为 $det$ 的矩阵 $A$,取值为一个标量,写作 $det(A)$ 或 $|A|$

逆序

对于 $n$ 个不同元素,有一个标准次序 $1,2,...,n$ 其下标为 $p_1,p_2,...,p_n$

一个逆序对即 $p_i>p_j$ 且 $i<j$ 的有序数对

一个序列的逆序即其逆序对总数

计算

设有 $n^2$ 个数,排成 $n \times n$ 的数表

\[\notag D= \begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix} \quad \]

令 $t$ 为列下标排列 $p_1p_2...p_n$ 的逆序数

则 $D=\sum (-1)^t a_{1 p_1} a_{2p_2}\cdots a_{n p_n}$

性质

...直接爆算

意义

从几何上来看行列式 $R^n$ 是 $n$ 维空间下几何的体积

组合计数

加法原理

若完成一件事的方法有 $n$ 类,其中第 $i$ 类方法包括 $a_i$ 种不同的方法,且这些方法互不重和

则完成这件事共有 $a_1+a_2+...+a_n$ 种不同的方法

乘法原理

若完成一件事需要 $n$ 个步骤,其中第 $i$ 步骤有 $a_i$ 种不同的完成方法,且这些步骤互不干扰

则完成这件事共有 $a_1\times a_2 \times ... \times a_n$ 种不同的方法

排列数

从 $n$ 个不同元素一次取出 $m$ 个元素排成一列,产生的不同排列的数量(记为 $P$ )

则 $P_n^m=\dfrac{n!}{(n-m)!}$

多重集合的排列数

设 $S=\{n_1\cdot a_1,n_2 \cdot a_2 ,...,n_k \cdot a_k \}$ 是一个多重集,则 $S$ 的全排列个数为 $\dfrac{n!}{n_1!n_2!...n_k!}$

多重集合的组合数

设 $S=\{n_1\cdot a_1,n_2 \cdot a_2 ,...,n_k \cdot a_k \}$ 是一个多重集,则从 $S$ 中取 $r$ 个组成的多重集(不考虑元素顺序)数量为 $C_{n+r-1}^{k-1}$

组合数

从 $n$ 个不同元素依次取出 $m$ 个元素组成与一个集合(不考虑顺序),产生的不同集合的数量(记为 $C$ )

则 $C_n^m=\dfrac{n!}{m!(n-m)!}$

性质

$C_n^m=C_n^{n-m}$
$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
$C_n^0+C_n^1+...+CN-^n=2^n$

二项式定理

有 $(a+b)^n=\sum\limits_{k=0}^n C_n^ka^kb^{n-k}$

Lucas 定理

若 $p$ 是质数,则对于任意的 $1\le m \le n$ 有

\[\notag C_n^m=C^{m \mod p}_{n \mod p} \times C^{m/p}_{n/p} \]

有

int C(int n,int m); //计算组合数
//
int Lucas(int n,int m,int p)
{
	if(m==0) return 1;
    return (C(n%p,m%p)*Lucas(n/p,m/p,p)%p)%p;
}

Catalan 数

一个定义:给定 $n$ 个 $0$ 和 $n$ 个 $1$ ,它们按某种顺序排成的长度长为 $2n$ 的序列,满足任意前缀 $0$ 的个数都不少于 $1$ 的个数的序列的数量为 $Catalan_n=\dfrac{C_{2n}^n}{n+1}$

概率与期望

概率

设样本空间为 $\Omega$ ,若对于 $\Omega$ 中的每一个随机事件 $A$ ,都存在实数 $P(A)$ 满足

$P(A)\ge 0$
$P(\Omega)=1$
对于若干个两两互斥的事件 $A_1,A_2,...$ 有 $\Sigma P(A_i)=P(\cup A_i)$ 其中 $\cup$ 表并集

则称 $P(A)$ 是随机事件 $A$ 发生的概率

期望

若随机变量 $X$ 的取值有 $x_1,x_2,...$ ,一个随机事件可表示为 $X=X_i$ ,其概率为 $P(X=X_i)=p_i$ ,则称 $E(x)=\Sigma p_i x_i$ ,为随机变量 $X$ 的数学期望

亦为随机变量取值与概率的乘积之和

数学期望为线性函数满足 $E(aX+bY)=aE(X)+bE(Y)$

字符串

Trie

struct trie{
	int next[MAX][26],cnt;
    bool exist[MAX];
    void insert(char *s,int len)
    {
    	int p=0;
        for(int i=0;i<len;i++)
        {
        	int c=s[i]-'a';
            if(!next[p][c]) next[p][c]=++cnt;
            p=next[p][c];
        }
        exist[p]=1;
    }
    bool find(char *s,int len)
    {
    	int p=0;
        for(int i=1;i<len;i++)
        {
        	int c=s[i]-'a';
            if(!next[p][c]) return 0;
            p=next[p][c];
        }
        return exist[p];
    }
};

搜索

DFS

int dfs(_state())
{
	if(_end()) return _update(_ans());
    _change(_state());
    _solve(_state());
    dfs(_anotherState());
	_restore(_state());
}

BFS

int bfs()
{
	queue<_stateDATA> q;
	q.push(_startState()); _set(check[_startState()],1);
    while(!q.empty())
    {
        _stateDATA now=q.front(); q.pop();
        if(check[now]) continue;
        check[now]=1;
        _solve(now);
        q.push(_anotherState());
    }
    return _ans();
}

A*

有开始的代价 $g(x)$ 到终点的代价 $h(x)$ 令 $f(x)=g(x)+h(x)$

如果 $h(x)\le h*(x)$ A* 一定能找到最优解

当 $h=0$ $A^*$变为 DFS 当 $h=0$ 且边权为 $1$ $A^*$ 变为 BFS

int bfs()
{
	priority_queue<_stateDATA(_cmpf())> q; //greater_priority_queue
	q.push(_startState(),f(_startState()));
    while(!q.empty())
    {
        _stateDATA now=q.top(); q.pop();
        _solve(now);
    	if(_ans()==_need()) return _ans();
        q.push(_anotherState(),f(_anotherState()));
    }
    return _ans();
}
int f(int x)
{
	return _g(x)+_h(x);
}

迭代加深

int dfs(_state(),deep)
{
    if(deep>_limit()) return _ans();
	if(_end()) return _ans();
    _change(_state());
    _solve(_state());
    dfs(_anotherState(),deep+1);
	_restore(_state());
}

分治

普通分治

int function(int l,int r)
{
	if(_solveEasily()) return _solve();
    mergeFonction(fonction(l,mid),function(mid+1,r));
}

cdq分治

将一个区间 $[l,r]$ 分成 $[l,mid],[mid+1,r]$ 求解左区间对右区间的贡献

重要的是将问题的规模减半

点分治

杂项

枚举

顺序

void solve()
{
	int A=_init();
    _sort(A);
    do{
    	_solve(A);
    }while(next_permutation(A)); //倒序prev_permutation(A)
}

划分

for(int S=0;S<(1<<MAX);S++)
{
	_solve(S);
}

二分

int search(int L,int R)
{
	int l=L,r=R,ans;
    while(l<=r)
    {
    	int mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
bool check(int mid) {return _check();}

三分

const double esp=1e-6;
//
double search(double L,double R)
{
	double l=L,r=R;
    while(r-l>=esp)
    {
    	double t=(r-l)/3;
        if(solve(l+t)>solve(r-t)) r-=t;
        else l+=r;
    }
    return t;
}
double solve(double x) {return _solve();}

模拟退火

卡时 while((double)_startTime()<=LIMIT_TIME) SA();

void SA()
{
	double t=_originalT();
	_data _state();
	while(t>_endT())
    {
        _date _newState();
        double now=solve(_newState());
        double delta=now-ans;
        if(_canAccept(now)) _accept(_newState());
        else if(exp(-delta/t)*RAND_MAX>rand()) _accept(_newState());
        t=t*_delta();
    }
}

文件IO

freopen

freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
//

//
fclose(stdin);
fclose(stdout);

fstream

ifstream fin("xxx.in");
ofstream fout("xxx.out");
//

//
fin.close();
fout.close();

码农公寓

图论

生成树

Kruskal

Prim

重链剖分

最近公共祖先(LCA)

树链剖分

倍增

最短路

Dijkstra

SPFA

Floyd

Johnson

网络流

Dinic

数据结构

并查集

堆

STL

手写

树状数组

单修区查

区修单查

线段树

ST表

平衡树

Fhq-Treap

Splay

珂朵莉树

分块

数学

快速幂

质数

素数分布定理

算术基本定理

算术基本定理的推论

线性筛

同余

费马小定理

欧拉定理

扩展欧拉定理

逆元

线性求逆元

拓展欧几里得求逆元

费马小定理求逆元

最大公约数

最大公约数定理

辗转相除法

拓展欧几里德算法

积性函数

欧拉函数

欧拉函数

筛法

线性基

同余方程

线性同余方程

中国剩余定理

拓展中国剩余定理

BSGS

矩阵

运算

加减法

乘法

数乘

矩阵相乘

性质

加减

数乘

乘

转置矩阵

性质

单位矩阵

余子式

代数余子式

伴随矩阵

逆矩阵

性质

运算规律

线性方程组