# ㄌㄌㄎ的魔法書

## vim ~/.vimrc

syntax on
set cin nu si ai ic ts=4 sw=4 bs=2 bg=dark 
inoremap {<CR> {<CR><END><CR>}<UP><END>

## 0.cpp

#include <bits/stdc++.h>

using namespace std;
#define INITIO()    (ios::sync_with_stdio(0), cin.tie(0))
#define MEM(i,j)    memset(i,j,sizeof i);
#define X           first
#define Y           second
#define pb          push_back
#define mp          make_pair
#define ALL(a)      a.begin(),a.end()
typedef             long long ll;
typedef             long long Int;
typedef             pair<int ,int> pii;
const double Eps  = 1e-8;
const ll Inf      = 1e18+7;
const int Mod     = 1e9+7;

void solve(){

}

int main (){
    INITIO();
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

## DSU

void ini(){
    for(int i=0;i<N;i++) d[i]=i;
}

int find(ll v){
    if(d[v]==v) return v;
    return d[v] = find(d[v]);
}

void union(ll a,ll b){
    d[find(a)] = find(b);
}

## MST

typedef struct{
    ll a,b,w;
}Edge;

### Kruskal
$O(Elog(E))$

bool cmp(Edge a,Edge b){
    return a.w<b.w;
}

Edge e[M];
ll d[N];

...

sort(e,e+m,cmp);

for(int j=0;j<m;j++){
    if(find(e[j].a) == find(e[j].b)) continue;
    d[find(e[j].a)] = find(e[j].b);
    cost+=e[j].w;
    MST.pb(Edge(e[j].a,e[j].b,w));
}

### Prim's
$O((E+N)log(E+N))$

priority_queue<Edge> q;
q.push((Edge){1,1,0}); //root

while(q.size()){
    int a = (q.top()).a, b = (q.top()).b, w = (q.top()).w;
    q.pop();
    
    if(!vis[b]){
        cost += w;
        MST.pb(Edge(a,b,w));
        for (auto it :　Ｅ[b]) if(!vis[it.n]) q.push(Edge(b,it.n.it.w));
    }
    vis[b] = true;
}

## Segments tree

struct Seg {
	int l, r, m;
	Int mx;
	Seg* ch[2];
	Seg (int _l, int _r, vI &a) : l(_l), r(_r), m((l + r)/2) {
		if (r - l > 1) {
			ch[0] = new Seg(l, m, a);
			ch[1] = new Seg(m, r, a);
			mx=max(ch[0]->mx,ch[1]->mx);
		} else {
			mx = a[l];
		}
	}
	Int query(Int ql , Int qr){
		if (ql <= l && r <= qr) return mx;
		Int ans=0; 
		if(qr<=m) ans = ch[0]->query(ql,qr);
		else if(ql>=m) ans = ch[1]->query(ql,qr);
		else ans = max(ch[0]->query(ql,m),ch[1]->query(m,qr));
		return ans;
	}
	void modify(Int x , Int v){
		if(r-l==1) {
			mx = v;
			return;
		}
		if(x<m) ch[0]->modify(x,v);
		else ch[1]->modify(x,v);
		mx=max(ch[0]->mx,ch[1]->mx);
	}
};

## Dijkstra
單點搜尋
$O((E+N)log(N))$

struct Node{
    ll n,w;
    bool operator<(const node &lhs) const {
        return lhs.w < w; //min heap
    }
};

初始:

MEM(dist,Inf); //不連通設Inf
MEM(vis,false); //沒有拜訪
priority_queue<Node> q;
q.push((Node){1,dist[1]=0}); //看起點更改

循環:

while(q.size()){
    node now = q.top();q.pop();
    vis[now.n] = true;
    
    for(auto nxt : e[now.n]){
        if(vis[nxt.n]) continue;
        const int &updater = dist[now.n] + nxt.w; 
        if(update < dist[nxt.n]) {
            dist[nxt.n] = update; //鬆弛
            q.push((Node){nxt.n,dist[nxt.n]});
        }
    }
}

## Bellman-Ford+檢查負環
單點搜尋
$O(NE)$

int w[N][N];
int d[N];
int parent[N];

void bellman_ford(int source){
    for(int i=0;i<n;i++) d[i]=Inf;
    d[source] = 0;
    parent[source] = source;
    
    for(int i=0;i<n-1;i++)
        for(int a=0;a<n;++a)
            for(int b=0;b<n;b++)
                if(d[a] != Inf && w[a][b] != Inf)
                    if(d[a]+w[a][b] < d[b]){
                        d[b] = d[a] + w[a][b];
                        parent[b] = a;
                    }
}

負環檢查
* 如果還能鬆弛代表有負環

bool is_negative(){
    for(int a=0;a<n;++a)
        for(int b=0;b<n;++b)
            if(d[a] != Inf && w[a][b] != Inf)
                if(d[a]+w[a][b] < d[b])
                    return true;
        
    
    return false;
}

遞迴版本 視情況修改 (一開始刻我以為是 dijkstra,但能處理處理負環)

ll bell(int start,int end,int val){
    ll ans = Inf;
    
    if(dis[start]<=val) return Inf;
    else dis[start] = val;
    if(start == end) return val;

    for(int i=0;i<E[start].size();i++) 
        ans = min(ans,bell(E[start][i].X,end,E[start][i].Y+val));

    return ans;
}

## Floyd-Warshell + 檢查負環
$O(N^3)$
多源搜尋

for(int i = 0;i<n ;i++){
    for(int j =0;j<n ;j++){
        if(i == j) dp[i][j] = 0;
        else dp[i][j] = Inf;
    }
}
...
for(int k =0;k<n;k++)
    for(int i=0;i<n;i++)
        for(int j = 0;j <n;j++)
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);

負環

bool is_negative(){
    for (int i=0; i<n; i++)
        if (d[i][i] < 0) //自己到自己必須是0否則有負環
            return true;
    return false;
}

## AP 關節點

void dfs(int prec,int cur,int dep){
    lvl[cur] = top[cur] = dep+1;
    int child = 0;
    for(itn nxt = 1;nxt <= n ; nxt++) if(E[cur][nxt] && nxt!= prev){
        if(!lvl[nxt]){
            child++,dfs(cur,nxt,dep+1);
            if(dep && top[nxt] >= lvl[cur]) AP.insert(cur);
            else top[cur] = min(top[cur],top[nxt]);
        }else top[cur] = min(top[cur],lvl[nxt]);
    }
}

## Max flow

int max_flow = 0;
while(1){
    MEM(vis,false);
    MEM(flow,false);
    queue<int> q;
    q.push(s); vis[s] = true; flow[s] = Inf;
    
    while(q.size()){
        int u=q.front();q.pop();
        for(int v=s;v<=t;v++) if(R[u][v] && !vis[v]){
            q.push(v);vis[v] = true;
            flow[v] = min(flow[u],R[u][v]);
            pre[v]=u;
        }
    }
    if(flow[t]==0) break;
    
    for(int v=t;v!=s;v=pre[v]){
        int u = pre[v];
        R[u][v] -= flow[t];
        R[v][u] += flow[t];
    }max_flow += flow[t];
}

## SCC
強連通 : 每個頂點皆能經由該圖邊抵達其他的每一個點的有向圖

void forward(int u){
    vis[u] = true;
    for(int v = 0;v < maxn;v++) if(E[u][v] && !vis[v]) forward(v);
    st.push(u);
}
void backward(){
    vis[u] = true;
    for(int v=0;v<maxn;v++) if(E[u][v] && !vis[v]) backward(v); 
}

循環

for(int u=0;u<n;u++) if(!vis[u]) forward(u);

MEM(vis,0);
int cnt = 0;
while(!st.empty()){
    int node = st.top(); st.pop();
    if(!vis[node]) cnt++,backward(node); 
}

## 快速冪

ll Power(ll n,ll time){
    ll a = 1;
    while(time){
        if(time & 1) a = a*n % Mod;
        n = n*n % Mod;
        time>>=1;
    }
    return a;
}

## 線性篩法

bool arr[n+1];
for(int i=2;i*i<=n;++i)
    if(!arr[i]) 
        for(int j = i*i ; j<=n ;j+=i) 
            arr[j] = true;

## KMP
找到 b 字串在 a 字串的最小位置

int pmatch(string a,string b){
    int i=0,p=-1;
    while(i<a.length()&&p+1<b.length()){
        if(a[i]==b[p+1]){i++;p++;}
        else if(p==-1) i++;
        else p = f[p];
    }
    return (p+1 == b.length()?i-b.length():-1);
}

void fail(string pat){
    int p = f[0] =-1;
    for(int i=1;i<pat.length();i++){
        while(p!=-1 && pat[i]!=pat[p+1]) p=f[p];
        if(pat[p+1]==pat[i]) p++;
        f[i] = p;
    }
}

## GCD

int gcd(int a, int b)
{ return a? gcd(b%a, a) : b;}

### 貝祖等式 (Bezout’s Thm)
>對整數 **a,b** , 存在整數 **x,y** 使得 **ax+by = gcd(a,b)**

### 擴展歐基里德
令 **g = gcd(0,g) = gcd(a,b)**

int gcd(int a, int b, int &x, int &y) {
  if(!a) {
    x = 0; // x 為任意整數 
    y = 1;
    return b;
  }

  int g = gcd(b%a, a, x, y);
  int xp = y - b/a * x, yp = x; // p := previous
  x = xp, y = yp;

  return g;
}

**exgcd** 可求模反元素 x, 但僅於 a 跟 b 互質