---
# System prepended metadata

title: 競賽模板

---

# 競賽模板
ac自动机fail树上dfs序建可持久化线段树
后缀自动机的next指针DAG图上求SG函数

## 一些數
### 質數
999961
999979
999983

998244353
1000000009
1000000007
### 黃金比例常數
0x9e3779b97f4a7c15ULL

## DP




### 0/1Knapsack
#### 重量限制小
```cpp
for(int i=1;i<=n;++i) cin>>w[i]>>v[i];
for(int i=1;i<=n;++i){
    for(int j=m;j>=w[i];--j){
        dp[j]  = max(dp[j],dp[j-w[i]]+v[i]);
    }
}
cout<<dp[m]<<endl;
```
#### 重量限制大、物品價值小
```cpp
    for(int i=1;i<=n;++i) cin>>w[i]>>v[i];
    for(int i=1;i<maxn;++i) dp[i] = inf;
    for(int i=1;i<=n;++i){
        for(int j=maxn-1;j>=v[i];--j){
            dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    for(int i=maxn-2;i>=1;--i){
        if(dp[i] <= m) {cout<<i<<endl; break; }
    }
```
### 有限背包 O(NM) 單調對列優化
```cpp
for(int i=1;i<=n;++i){
    for(int mod = 0;mod<p[i].w;++mod){
        Q.clear();
        for(int j=mod;j <= T;j += p[i].w){
            val[j] = dp[j] - (j/p[i].w)*p[i].v;
            while(!Q.empty() && val[Q.back()] <= val[j])
                Q.pop_back();
            Q.push_back(j);
            dp[j] = val[Q.front()] + (j/p[i].w)*p[i].v;
            if(Q.front() == j-p[i].w*p[i].c)
                Q.pop_front();
        }
    }
}

```

### LCS (回朔解)
```cpp
ls = s.size(), lt = t.size();
s = ' '+s, t = ' '+t;
for(int i=1;i<=ls;++i){
    for(int j=1;j<=lt;++j){
        if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1] + 1, d[i][j] = 1;
        else dp[i][j] = max(dp[i-1][j],dp[i][j-1]), d[i][j] = (dp[i-1][j] > dp[i][j-1])?2:3;
    }
}
int x = ls,y = lt;
while(x >= 1 && y >= 1){
    if(d[x][y] == 1) as += s[x], x--, y--;
    else if(d[x][y] == 2) x--;
    else y--;
}
reverse(as.begin(),as.end());
cout<<as<<endl;
```
### LIS (嚴格遞增)
```cpp
for(int i=1;i<=n;++i){
    if(dp.empty() || arr[i] > dp.back()){
        dp.push_back(arr[i]);
    }else{
        auto it = lower_bound(dp.begin(),dp.end(),arr[i]);
        *it = arr[i];
    }
}
lis = dp.size();
```

### 回朔 LIS (非嚴格遞增)

```cpp 
for(int i=1;i<=n;++i){
    if(dp.empty() || dp.back() <= p[i]){
        dp.push_back(p[i]);
        int tmp = dp.size();
        id[tmp] = i;
        if(tmp > 1) pre[i] = id[tmp-1];
    }else{
        int it = upper_bound(dp.begin(),dp.end(),p[i])-dp.begin();
        dp[it] = p[i];
        it++;
        id[it] = i;
        if(it > 1) pre[i] = id[it-1];
    }
}
int len = dp.size();
int pos = id[len];
vector<int> tmp;
tmp.push_back(id[len]);
for(int i=1;i<len;++i){
    pos = pre[pos];
    tmp.push_back(pos);
}
reverse(tmp.begin(),tmp.end());
```

### 樹背包
```cpp

const LL mod = 998244353;

LL n,dp[maxn][maxn][.];
int sz[maxn];
vector<int> E[maxn];

void dfs(int x,int p){
    sz[x] = 1;
    // init
    for(int i:E[x]){
        if(i==p) continue;
        dfs(i,x);
        int oS = sz[x];
        int C = sz[i];
        sz[x] += sz[i];
        int S = sz[x];
        vector<LL> s0(S+1),s1(S+1); // 算極值要初始化
        for(int a=0;a<=oS;++a){
            for(int b=0;b<=C;++b){
                // update
            }
        }
        for(int k=0;k<=S;++k){
            dp[x][k][.] = s0[k];
            dp[x][k][.] = s1[k];
        }
    }
}

```

### 迴圈式數位DP
ex : ABC235F
```cpp
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
const LL inf = 1e18, maxn = 200005, mod = 998244353;

int n,m,reqmask;
LL pres,premask;
string s;

inline void add(LL &x,const LL&a){
    x = (x+a)%mod;
}

main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>s>>m;
    for(int i=1;i<=m;++i){
        int a; cin>>a;
        reqmask |= (1<<a);
    }
    n = s.size();
    vector<LL> dps(1<<10),dpc(1<<10);
    for(int d=0;d<n;++d){
        vector<LL> nds(1<<10),ndc(1<<10);
        for(int S=1;S<(1<<10);++S){
            for(int i=0;i<=9;++i){
                int nm = S|(1<<i);
                add(ndc[nm],dpc[S]);
                add(nds[nm],(dps[S]*10%mod+i*dpc[S]%mod)%mod);
            }
        }
        if(d!=0){
            for(int i=1;i<=9;++i){
                int nm = (1<<i);
                add(ndc[nm],1);
                add(nds[nm],i);
            }
        }
        int c = s[d]-'0';
        for(int i=(d==0?1:0);i<c;++i){
            int nm = premask|(1<<i);
            add(ndc[nm],1);
            add(nds[nm],(pres*10%mod+i)%mod);
        }
        dps.swap(nds);
        dpc.swap(ndc);
        premask |= (1<<c);
        pres = (pres*10%mod+c)%mod;
    }
    LL as = 0;
    for(int i=1;i<(1<<10);++i){
        if((i&reqmask) == reqmask) add(as,dps[i]);
    }
    if((premask&reqmask) == reqmask) add(as,pres);
    cout<<as<<endl;
}




```

### 無分支版 SOS

```cpp
for(int i=0;i<D;++i){
    int tmp = (1<<i);
    for(int j=0;j<(1<<D);j+=(tmp<<1)){
        for(int k=0;k<tmp;++k){
            dp[k+j+tmp] += dp[k+j];
        }
    }
}
```

## 圖論

### MST (prim) O(ElogV)
```cpp
int primMST(int s){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q;
    bitset<maxn> vi;
    Q.push({0,s});
    int sum = 0;
    while(!Q.empty()){
        auto x = Q.top(); Q.pop();
        if(vi[x.second]) continue;
        sum += x.first;
        vi[x.second] = 1;
        for(auto i:E[x.second]){
            if(!vi[i.first]) Q.push({i.second,i.first});
        }
    }
    return sum;
}
```
### MST (prim) O(n^2) 用於完全圖
dis[i] : i到MST的最小距離
```cpp
for(int i=1;i<=n;++i) dis[i] = inf;
int as = 0, id = 1;
dis[1] = 0;
for(int i=1;i<=n;++i){
    vi[id] = 1;
    for(int j=1;j<=n;++j){
        if(vi[j]) continue;
        dis[j] = min(dis[j],cal(id,j));
    }
    int mn = inf;
    as += dis[id];
    for(int j=1;j<=n;++j){
        if(vi[j]) continue;
        if(dis[j] < mn){
            mn = dis[j];
            id = j;
        }
    }
}
```
### 拓譜排序
```cpp
void dfs(int x){
    vi[x] = 1;
    for(int i:E[x]) nif(!vi[i]) dfs(i);
    tp.push_back(x);
}
main(){
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int a,b; cin>>a>>b;
        E[a].push_back(b);
    }
    for(int i=1;i<=n;++i) if(!vi[i]) dfs(i);
    reverse(tp.begin(),tp.end());
}
```

### 二分圖最大匹配
```cpp
int n,k,ma[maxn],mb[maxn];
vector<int> E[maxn];
bitset<maxn> vi;
bool dfs(int x){
    vi[x] = 1;
    for(int i:E[x]){
        if(!~mb[i] || (!vi[mb[i]] && dfs(mb[i]))){
            ma[x] = i;
            mb[i] = x;
            return 1;
        }
    }
    return 0;
}
main(){
    for(int i=1;i<=n;++i) ma[i] = mb[i] = -1;
    int as = 0;
    for(int i=1;i<=n;++i){
        vi.reset();
        if(dfs(i)) as++;
    }
}

```

### SPFA
if(!Q.empty() && cost[i.v] < cost[Q.front()]) Q.push_front(i.v);
else Q.push_back(i.v);
優化
```cpp
void SPFA(int s){
    for(int i=1;i<=n;++i) cnt[i] = in[i] = 0, dis[i] = inf;
    queue<int> Q;
    Q.push(s); in[s] = 1;
    dis[s] = 0;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        in[x] = 0;
        if(++cnt[x] >= n){
            cout<<"find nag"<<endl;
        }
        for(auto i:E[x]) if(dis[x]+i.second < dis[i.first]){
            dis[i.first] = dis[x] + i.second;
            if(!in[i.first]) Q.push(i.first), in[i.first] = 1;
        }
    }
}
```
### dij
```cpp!
struct comp{
    bool operator()(const pair<int,int>&a,const pair<int,int>&b){
        return a.second > b.second;
    }
};
priority_queue<pair<int,int>,vector<pair<int,int>>,comp> Q;
vector<pair<int,int>> E[maxn];
bitset<maxn> vi;
void dij(int s,int dis[]){
    for(int i=1;i<=n;++i) dis[i] = inf;
    dis[s] = 0;
    Q.push({s,0});
    vi.reset();
    while(!Q.empty()){
        auto x = Q.top(); Q.pop();
        if(vi[x.first]) continue;
        vi[x.first] = 1;
        for(auto i:E[x.first]){
            if(vi[i.first]) continue;
            if(dis[i.first] > dis[x.first]+i.second){
                dis[i.first] = dis[x.first] + i.second;
                Q.push({i.first,dis[i.first]});
            }
        }
    }
}

```

### 歐拉迴路 / 路徑
```cpp
void dfs(int x){
    vi[x] = 1;
    while(!E[x].empty()){
        int i = *E[x].begin();
        E[x].erase(i);
        E[i].erase(x);
        cnt++;
        dfs(i);
    }
    as.push_back(x);
}
```
### SCC (Kosaraju's Algorithm)
```cpp
int n,m,sn,scc[maxn];
vector<int> E[maxn],pE[maxn],tp;
bitset<maxn> vi;
void dfs1(int x){
    vi[x] = 1;
    for(int i:E[x]){
        if(!vi[i]) dfs1(i);
    }
    tp.push_back(x);
}
void dfs2(int x){
    scc[x] = sn;
    for(int i:pE[x]){
        if(!scc[i]) dfs2(i);
    }
}
main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int a,b; cin>>a>>b;
        E[a].push_back(b);
        pE[b].push_back(a);
    }
    for(int i=1;i<=n;++i) if(!vi[i]) dfs1(i);
    reverse(tp.begin(),tp.end());
    for(int i=0;i<n;++i){
        if(!scc[tp[i]]){
            sn++;
            dfs2(tp[i]);
        }
    }
}
```
### 關節點
```cpp
int n,m,dfn[maxn],low[maxn],timer,isap[maxn];
vector<int> E[maxn];
void dfs(int x,int p){
    dfn[x] = low[x] = ++timer;
    int cnt = 0;
    for(int i:E[x]){
        if(i == p) continue;
        if(!dfn[i]){
            cnt++;
            dfs(i,x);
            low[x] = min(low[x],low[i]);
            if(low[i] >= dfn[x] && p!=0){
                isap[x] = 1;
            }
        }else if(dfn[i] < dfn[x]){
            low[x] = min(low[x],dfn[i]);
        }
    }
    if(p==0 && cnt >= 2){
        as.push_back(1);
    }
}
```

### 橋
```cpp
int n,m,dfn[maxn],low[maxn],timer;
vector<int> E[maxn];
vector<pair<int,int>> br;
void dfs(int x,int p){
    low[x] = dfn[x] = ++timer;
    for(int i:E[x]){
        if(i == p) continue;
        if(!dfn[i]){
            dfs(i,x);
            low[x] = min(low[x],low[i]);
            if(low[i] > dfn[x]){
                br.push_back({i,x});
            }
        }else if(dfn[i] < dfn[x]){
            low[x] = min(low[x],dfn[i]);
        }
    }
}
```
### 邊雙連通分量
E[x].first : 點編號
E[x].second : 邊編號
```cpp
int n,m,dfn[maxn],low[maxn],timer,bcnt,bcc[maxn]; // 這個點屬於哪個bcc
vector<pair<int,int>> E[maxn];
vector<int> inbcc[maxn];  // 這個bcc有哪些點
stack<int> st;
void dfs(int x,int p){
    low[x] = dfn[x] = ++timer;
    st.push(x);
    for(auto i:E[x]){
        if(i.second == p) continue;
        if(!dfn[i.first]){
            dfs(i.first,i.second);
            low[x] = min(low[x],low[i.first]);
            if(low[i.first] > dfn[x]){
                bcnt++;
                while(st.top() != i.first)
                    bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
                bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
            }
        }else if(dfn[i.first] < dfn[x]){
            low[x] = min(low[x],dfn[i.first]);
        }
    }
    if(p == 0){
        bcnt++;
        while(st.top() != x)
            bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
        bcc[st.top()] = bcnt, inbcc[bcnt].push_back(st.top()), st.pop();
    }
}
```
### 點雙連通分量
```cpp
void dfs(int x,int p){
    low[x] = dfn[x] = ++timer;
    st.push(x);
    for(int i:E[x]){
        if(i == p) continue;
        if(!dfn[i]){
            dfs(i,x);
            low[x] = min(low[x],low[i]);
            if(low[i] >= dfn[x]){
                bcnt++;
                ap[x] = 1;
                while(st.top() != i){
                    in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
                    st.pop();
                }
                in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
                st.pop();
                in_bcc[x].push_back(bcnt);
                bcc[bcnt].push_back(x);
            }
        }else if(dfn[i] < dfn[x]){
            low[x] = min(low[x],dfn[i]);
        }
    }
}
```
### Block-Cut Tree (點雙縮點)
```cpp
vector<int> E[maxn],bE[maxn*2];
int n,m,q,low[maxn],dfn[maxn],timer,ap[maxn],bcnt;
vector<int> bcc[maxn],in_bcc[maxn];
stack<int> st;
void dfs(int x,int p){
    low[x] = dfn[x] = ++timer;
    st.push(x);
    for(int i:E[x]){
        if(i == p) continue;
        if(!dfn[i]){
            dfs(i,x);
            low[x] = min(low[x],low[i]);
            if(low[i] >= dfn[x]){
                bcnt++;
                ap[x] = 1;
                while(st.top() != i){
                    in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
                    st.pop();
                }
                in_bcc[st.top()].push_back(bcnt); bcc[bcnt].push_back(st.top());
                st.pop();
                in_bcc[x].push_back(bcnt);
                bcc[bcnt].push_back(x);
            }
        }else if(dfn[i] < dfn[x]){
            low[x] = min(low[x],dfn[i]);
        }
    }
}
main(){
    cin>>n>>m>>q;
    for(int i=1;i<=m;++i){
        int a,b; cin>>a>>b;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i){
        if(in_bcc[i].size()>1){
            for(int j:in_bcc[i]){
                bE[i+bcnt].push_back(j);
                bE[j].push_back(i+bcnt);
            }
        }
    }
}

```

### 線段樹優化建圖
```cpp!

#define maxn 100005
const int D = maxn*4;
int n,m,to[maxn];
vector<pair<int,int>> E[maxn*8];
void build(int l,int r,int x){
    if(l==r){
        to[l] = x;
        E[x].push_back({x+D,0});
        E[x+D].push_back({x,0});
        return;
    }
    int ls = x*2 ,rs = ls+1,mid = (l+r)/2;
    E[x].push_back({ls,0}); E[x].push_back({rs,0});
    E[ls+D].push_back({x+D,0}); E[rs+D].push_back({x+D,0});
    build(l,mid,ls);
    build(mid+1,r,rs);
}
void modify(int a,int b,int l,int r,int x,int v,int w,int op){
    if(l>=a&&r<=b){
        if(!op) E[x+D].push_back({to[v],w});
        else E[to[v]].push_back({x,w});
        return;
    }
    int ls = x*2, rs = ls+1, mid = (l+r)/2;
    if(mid >= a) modify(a,b,l,mid,ls,v,w,op);
    if(mid < b) modify(a,b,mid+1,r,rs,v,w,op);
}
```

### Dinic’s Algorithm
```cpp
struct EDG{
    int v,f,re;
};
int n,m,st,ed,it,d[maxn];
vector<int> E2[maxn];

inline void con(int a,int b,int c){
    E[a].push_back({b,c,(int)E[b].size()});
    E[b].push_back({a,0,(int) E[a].size()-1});
}
bool bfs(){
    for(int i=1;i<=it;++i) d[i] = -1;
    queue<int> Q;
    Q.push(st);
    d[st] = 0;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        for(auto i:E[x]){
            if(i.f > 0 && d[i.v] == -1){
                d[i.v] = d[x] + 1;
                Q.push(i.v);
            }
        }
    }
    if(d[ed] == -1) return 0;
    return 1;
}
int dfs(int x,int nf){
    if(x == ed) return nf;
    int res = 0;
    for(auto &i:E[x]){
        if(i.f > 0 && d[i.v] == d[x]+1){
            int tf = dfs(i.v,min(nf,i.f));
            nf -= tf;
            i.f -= tf;
            res += tf;
            E[i.v][i.re].f += tf;
            if(nf == 0) return res;
        }
    }
    if(res == 0) d[x] = -1;
    return res;
}
```


### MCF
```cpp
struct EDG{
    int v,f,w,re;
};
int n,m,vi[maxn],inq[maxn],cost[maxn],pre[maxn],preid[maxn],st,ed,K;
vector<EDG> E[maxn];

inline void con(int a,int b,int c,int w){
    E[a].push_back({b,c,w,(int)E[b].size()});
    E[b].push_back({a,0,-w,(int)E[a].size()-1});
}
inline void init(){
    for(int i=1;i<=n;++i){
        cost[i] = inf;
        vi[i] = inq[i] = pre[i] = preid[i] = 0;
    }
}
pair<int,int> mcmf(){
    init();
    queue<int> Q;
    Q.push(st);
    cost[st] = 0;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        inq[x] = 0; vi[x] = 1;
        for(int id=0;id<E[x].size();++id){
            auto i = E[x][id];
            if(i.f > 0 && cost[i.v] > cost[x]+i.w){
                cost[i.v] = cost[x]+i.w;
                pre[i.v] = x;
                preid[i.v] = id;
                if(!inq[i.v]){
                    inq[i.v] = 1;
                    Q.push(i.v);
                }
            }
        }
    }
    if(vi[ed] == 0) return {0,0};
    int res = inf;
    for(int x = ed; x != st; x = pre[x]){
        res = min(res,E[pre[x]][preid[x]].f);
    }
    for(int x = ed; x != st; x = pre[x]){
        E[pre[x]][preid[x]].f -= res;
        E[x][E[pre[x]][preid[x]].re].f += res;
    }
    return {res,cost[ed]};
}


main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>K;
    st = 1;
    ed = n;
    for(int i=1;i<=m;++i){
        int a,b,c,d; cin>>a>>b>>c>>d;
        con(a,b,c,d);
    }
    int as = 0;
    while(K){
        pair<int,int> res = mcmf();
        if(res.first == 0){
            as = -1;
            break;
        }
        as += min(K,res.first)*res.second;
        K -= min(K,res.first);
    }
    cout<<as<<endl;
}

```

## 樹論
### 樹練剖分
```cpp
vector<int> E[maxn];
int n,hs[maxn],f[maxn],sz[maxn],d[maxn],val[maxn],tp[maxn],dfn[maxn],timer,arr[maxn],tree[maxn*4],q;
void dfs(int x,int p){
    sz[x] = 1;
    hs[x] = -1;
    for(int i:E[x]){
        if(i==p) continue;
        f[i] = x;
        d[i] = d[x]+1;
        dfs(i,x);
        sz[x] += sz[i];
        if(hs[x]==-1||sz[hs[x]] < sz[i]) hs[x] = i;
    }
}
void link(int x,int top){
    tp[x] = top;
    dfn[x] = ++timer;
    arr[timer] = val[x];
    if(hs[x]!=-1) link(hs[x],top);
    for(int i:E[x]){
        if(i==f[x] || i==hs[x]) continue;
        link(i,i);
    }
}
int jump(int a,int b){
    int mx = 0;
    while(tp[a]!=tp[b]){
        if(d[tp[b]]>d[tp[a]]) swap(a,b);
        mx = max(mx,query(dfn[tp[a]],dfn[a],1,n,1));
        a = f[tp[a]];
    }
    if(dfn[a]>dfn[b]) swap(a,b);
    mx = max(mx,query(dfn[a],dfn[b],1,n,1));
    return mx;
}

```
### 虛樹
lca.first : lca
lca.second : dis
```cpp
bool comp(int a,int b){
    return dfn[b] > dfn[a];
}
void dfs(int x,int p){
    dfn[x] = ++timer;
    for(int i:E[x]){
        if(i==p) continue;
        d[i] = d[x]+1;
        anc[i][0] = x;
        dfs(i,x);
    }
}

int lca(int a,int b){
    if(d[b] > d[a]) swap(a,b);
    int dh = d[a]-d[b];
    for(int i=0;i<=25;++i) if(dh&(1<<i)) a = anc[a][i];
    if(a==b) return a;
    for(int i=25;i>=0;--i){
        if(anc[a][i] != anc[b][i]){
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return anc[a][0];
}
inline void init(){
    for(int i:rec) E2[i].clear();
    rec.clear();
}
inline void con(int a,int b){
    E2[a].push_back(b);
    E2[b].push_back(a);
    rec.push_back(a);
    rec.push_back(b);
}
inline void build(vector<int> &h){
    sort(h.begin(),h.end(),comp);
    vector<int> tmp;
    int len = h.size();
    for(int i=0;i<len-1;++i){
        tmp.push_back(h[i]);
        tmp.push_back(lca(h[i],h[i+1]));
    }
    tmp.push_back(h.back());
    sort(tmp.begin(),tmp.end(),comp);
    tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
    for(int i=0;i<(int)tmp.size()-1;++i){
        int lc = lca(tmp[i],tmp[i+1]);
        con(tmp[i+1],lc);
    }
}
```

### 重心剖分(蓋重心樹)
```cpp
void dfs_sz(int x,int p){
    sz[x] = 1;
    for(int i:E[x]){
        if(i==p || vi[i]) continue;
        dfs_sz(i,x);
        sz[x] += sz[i];
    }
}
int find_c(int x,int p,int tot){
    for(int i:E[x]){
        if(i==p || vi[i]) continue;
        if(sz[i]*2 > tot) return find_c(i,x,tot);
    }
    return x;
}
void build_cd(int x,int p){
    dfs_sz(x,0);
    int c = find_c(x,0,sz[x]);
    vi[c] = 1;
    pa[c] = p;
    for(int i:E[c]){
        if(i==p || vi[i]) continue;
        build_cd(i,c);
    }
}

```

## 資節


### unordered pair hash

```cpp
struct phash{
    size_t operator()(const pair<int,int>& a) const{
        size_t h = 0;
        h ^= hash<int>{}(a.first) + 0x9e3779b97f4a7c15ULL + (h<<6) + (h>>2);
        h ^= hash<int>{}(a.second) + 0x9e3779b97f4a7c15ULL + (h<<6) + (h>>2);
        return h;
    }
};
```
### pbds
less_equal : multiset，lower_bound -> upper_bound
```cpp
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s2;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s1;
main(){
    s1.insert(3);
    s1.insert(5);
    s1.insert(7);
    s1.insert(9);
    int k = 3;
    cout<<*s1.find_by_order(k)<<endl; // an iterator of the (k+1)th smallest element
    cout<<s1.order_of_key(k)<<endl; // the number of elements are less than k
    s1.erase(s1.find(k)); //erase 要指標
}
```


### ST表
```cpp 
int n,m,arr[maxn],ST[20][maxn];
void build(){
    for(int i=1;i<=n;++i) ST[0][i] = arr[i];
    for(int k=1;(1<<k) <= n;++k){
        for(int i=1;i+(1<<k)-1 <= n;++i){
            ST[k][i] = min(ST[k-1][i],ST[k-1][i+(1<<(k-1))]);
        }
    }
}
int query(int l,int r){
    int k = __lg(r-l+1);
    return min(ST[k][l],ST[k][r-(1<<k)+1]);
}
```

### 帶權並查集
題目 : ABC 328 F - Good Set Query
```cpp
int findroot(int x){
    if(ds[x] == x) return x;
    int r = findroot(ds[x]);
    w[x] = w[x]+w[ds[x]];
    return ds[x] = r;
}
bool add(int a,int b,int v){
    int ra = findroot(a), rb = findroot(b);
    if(ra == rb) return w[b]-w[a] == v;
    ds[rb] = ra;
    w[rb] = v-(w[b]-w[a]);
    return true;
}
```
### two-stack trick
無法快速維護erase操作的雙指標問題
https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/G
```cpp
struct STK{
    stack<int> st,val;
    STK(){
        val.push(0);
    }
    bool empty(){
        return st.empty();
    }
    void push(int x){
        st.push(x);
        val.push(__gcd(val.top(),x));
    }
    void pop(){
        st.pop();
        val.pop();
    }
    int get(){
        return val.top();
    }
    int top(){
        return st.top();
    }
} s1,s2;

void ers(){
    if(s1.empty()){
        while(!s2.empty()){
            s1.push(s2.top());
            s2.pop();
        }
        s1.pop();
    }else{
        s1.pop();
    }
}
void add(int id){
    s2.push(arr[id]);
}
int query(){
    return __gcd(s1.get(),s2.get());
}
```
### 區間加值改值求和線段樹
```cpp
struct node{
    int tag1,tag2,sum;
    node(){
        tag1 = 0;
        tag2 = inf;
        sum = 0;
    }
};
node tree[maxn*4];
void mark1(int l,int r,int x,int v){
    tree[x].tag1 += v;
    tree[x].sum += v*(r-l+1);
}
void mark2(int l,int r,int x,int v){
    tree[x].tag2 = v;
    tree[x].sum = v*(r-l+1);
    tree[x].tag1 = 0;
}
void pushdown(int l,int r,int x){
    if(l==r) return;
    int ls = x*2, rs = ls+1, m =(l+r)/2;
    if(tree[x].tag2 != inf){
        mark2(l,m,ls,tree[x].tag2);
        mark2(m+1,r,rs,tree[x].tag2);
        tree[x].tag2 = inf;
    }
    if(tree[x].tag1){
        mark1(l,m,ls,tree[x].tag1);
        mark1(m+1,r,rs,tree[x].tag1);
        tree[x].tag1 = 0;
    }
}
void modify(int a,int b,int l,int r,int x,int v,int op){
    if(l>=a && r<=b){
        if(!op) mark1(l,r,x,v);
        else mark2(l,r,x,v);
        return;
    }
    int ls = x*2, rs = ls+1, m = (l+r)/2;
    pushdown(l,r,x);
    if(m >= a) modify(a,b,l,m,ls,v,op);
    if(m < b) modify(a,b,m+1,r,rs,v,op);
    tree[x].sum = tree[ls].sum + tree[rs].sum;
}
int query(int a,int b,int l,int r,int x){
    if(l>=a && r<=b) return tree[x].sum;
    int ls = x*2, rs = ls+1,m = (l+r)/2;
    pushdown(l,r,x);
    int res = 0;
    if(m >= a) res += query(a,b,l,m,ls);
    if(m < b) res += query(a,b,m+1,r,rs);
    return res;
}
```

### Merge Sort Tree
Count the numbers smaller than or equal to k in range [l,r]
```cpp
void build(int l,int r,int x){
    if(l == r){
        tree[x].push_back(arr[l]);
        return;
    }
    int ls = x*2,rs = ls+1, m = (l+r)/2;
    build(l,m,ls);
    build(m+1,r,rs);
    int sz1 = m-l+1, sz2 = r-m;
    int i = 0, j = 0;
    while(i<sz1 && j<sz2)
        tree[x].push_back((tree[ls][i] <= tree[rs][j])?tree[ls][i++]:tree[rs][j++]);
    while(i<sz1) tree[x].push_back(tree[ls][i++]);
    while(j<sz2) tree[x].push_back(tree[rs][j++]);
}
int query(int a,int b,int l,int r,int x,int k){
    if(l>=a && r<=b){
        auto it = upper_bound(tree[x].begin(),tree[x].end(),k);
        return it-tree[x].begin();
    }
    int ls = x*2, rs = ls+1, m = (l+r)/2;
    int sum = 0;
    if(m >= a) sum += query(a,b,l,m,ls,k);
    if(m < b) sum += query(a,b,m+1,r,rs,k);
    return sum;
}
```
### time segment tree　Ｘ　undoDSU
```cpp
struct EVENT{
    int st,et,a,b;
};
vector<EVENT> E;
vector<pair<int,int>> oper[maxn*4];
int n,m,k,as[maxn],ds[maxn],sz[maxn],cc;
stack<pair<int,int>> his;
map<pair<int,int>,int> mp;
 
void init(){
    cc = n;
    for(int i=1;i<=n;++i){
        sz[i] = 1;
        ds[i] = i;
    }
    while(!his.empty()) his.pop();
}
 
int findroot(int x){
    if(ds[x] == x) return x;
    return findroot(ds[x]);
}
void add(int a,int b){
    a = findroot(a), b = findroot(b);
    if(sz[b] > sz[a]) swap(a,b);
    his.push({a,b});
    sz[a] += sz[b];
    ds[b] = a;
    cc--;
}
void undo(){
    auto x = his.top(); his.pop();
    ds[x.second] = x.second;
    sz[x.first] -= sz[x.second];
    cc++;
}
void modify(int a,int b,int l,int r,int x,pair<int,int> edg){
    if(l>=a && r<=b){
        oper[x].push_back(edg);
        return;
    }
    int ls = x*2, rs = ls+1, m = (l+r)/2;
    if(m >= a) modify(a,b,l,m,ls,edg);
    if(m < b) modify(a,b,m+1,r,rs,edg);
}
void query(int l,int r,int x){
    int cnt = 0;
    for(auto i:oper[x]){
        if(findroot(i.first) != findroot(i.second)){
            cnt++;
            add(i.first,i.second);
        }
    }
    if(l==r) as[l] = cc;
    else{
        int ls = x*2, rs = ls+1, m = (l+r)/2;
        query(l,m,ls);
        query(m+1,r,rs);
    }
    while(cnt--){
        undo();
    }
}
```

### 持久化線段樹
```cpp
struct node{
    node *ls,*rs;
    int cnt;
    node():ls(nullptr),rs(nullptr),cnt(0){};
    void pull();
};
int n,q,arr[maxn],to[maxn];
node *root[maxn];

void node::pull(){
    cnt = ls->cnt+rs->cnt;
}
void build(int l,int r,node*x){
    if(l==r) return;
    int mid = (l+r)/2;
    x->ls = new node;
    x->rs = new node;
    build(l,mid,x->ls);
    build(mid+1,r,x->rs);
}
void modify(int a,int l,int r,node*x,node*pre,int v){
    if(l==r){
        x->cnt = v;
        return;
    }
    int mid = (l+r)/2;
    x->ls = pre->ls;
    x->rs = pre->rs;
    if(mid >= a){
        x->ls = new node{};
        modify(a,l,mid,x->ls,pre->ls,v);
    }else{
        x->rs = new node{};
        modify(a,mid+1,r,x->rs,pre->rs,v);
    }
    x->pull();
}
```

### 李超
```cpp
struct line{
    int a,b;
    line():a(0),b(inf){}
    line(int c,int d){
        a = c;
        b = d;
    }
    int operator()(const int x){
        return a*x+b;
    }
};
line tree[1000006*4];
void insert(int l,int r,int x,line L){
    int ls = x*2, rs = ls+1, mid = (l+r)/2;
    if(L(mid) < tree[x](mid)) swap(L,tree[x]);
    if(L.a == tree[x].a || l==r) return;
    if(L.a > tree[x].a) insert(l,mid,ls,L);
    else insert(mid+1,r,rs,L);
}
int query(int a,int l,int r,int x){
    int ls = x*2, rs = ls+1, mid = (l+r)/2;
    int res = tree[x](a);
    if(l==r) return res;
    if(mid >= a) res = min(res,query(a,l,mid,ls));
    else res = min(res,query(a,mid+1,r,rs));
    return res;
}
```


### 動態開點李超線段樹
```cpp
struct line{
    LL a,b;
    line(){
        a = 0;
        b = -inf;
    }
    line(LL c,LL d){
        a = c;
        b = d;
    }
    LL operator()(LL x){
        return x*a+b;
    }
};
struct node{
    node *ls,*rs;
    line L;
    node(){
        ls = rs = nullptr;
    }
};
void insert(int l,int r,node *x,line L){
    int mid = (l+r)/2;
    if(L(mid) > x->L(mid)) swap(x->L,L);
    if(l==r || L.a == x->L.a) return;
    if(L.a < x->L.a){
        if(x->ls == nullptr) x->ls = new node;
        insert(l,mid,x->ls,L);
    }
    else{
        if(x->rs == nullptr) x->rs = new node;
        insert(mid+1,r,x->rs,L);
    }
}
LL query(int a,int l,int r,node *x){
    if(x == nullptr) return -inf;
    LL res = x->L(a);
    int mid = (l+r)/2;
    if(l==r) return res;
    if(mid >= a) return max(res,query(a,l,mid,x->ls));
    else return max(res,query(a,mid+1,r,x->rs));
}

```
### treap (區間反轉區間min，可 logn 找元素位置)
```cpp
mt19937 rng(21342);

struct node{
    node *ls,*rs,*pa;
    int sz,pri,val,mn,tag;
    node(int v):ls(nullptr),rs(nullptr),pa(nullptr),sz(1),pri(rng()),val(v),mn(v),tag(0){}
};
node *node_of[maxn];

inline int size(node *a){
    if(a == nullptr) return 0;
    return a->sz;
}
inline int getmn(node *a){
    if(a == nullptr) return inf;
    return a->mn;
}
inline void pull(node *a){
    a->mn = min({getmn(a->ls),getmn(a->rs),a->val});
    a->sz = size(a->ls) + size(a->rs)+1;
    if(a->ls != nullptr) a->ls->pa = a;
    if(a->rs != nullptr) a->rs->pa = a;
}
inline void mark(node *a){
    if(a == nullptr) return;
    a->tag = !a->tag;
    swap(a->ls,a->rs);
}
inline void push(node *a){
    if(a == nullptr) return;
    if(a->tag){
        mark(a->ls);
        mark(a->rs);
        a->tag = 0;
    }
}

node *merg(node *a,node *b){
    if(a == nullptr){
        if(b != nullptr) b->pa = nullptr;
        return b;
    }
    if(b == nullptr){
        if(a != nullptr) a->pa = nullptr;
        return a;
    }
    if(a->pri < b->pri){
        push(a);
        a->rs = merg(a->rs,b);
        pull(a);
        a->pa = nullptr;
        return a;
    }else{
        push(b);
        b->ls = merg(a,b->ls);
        pull(b);
        b->pa = nullptr;
        return b;
    }
}
void split(node *p,node *&a,node *&b,int k){
    if(p == nullptr){
        a = nullptr;
        b = nullptr;
        return ;
    }
    push(p);
    if(size(p->ls) < k){
        a = p;
        split(a->rs,a->rs,b,k-size(p->ls)-1);
        pull(a);
    }else{
        b = p;
        split(b->ls,a,b->ls,k);
        pull(b);
    }
    if(a != nullptr) a->pa = nullptr;
    if(b != nullptr) b->pa = nullptr;
}

inline void rev(node *&root,int l,int r){
    node *a,*b,*c;
    split(root,a,b,r);
    split(a,a,c,l-1);
    mark(c);
    root = merg(merg(a,c),b);
}

void push_path(node *x){
    vector<node*> tmp;
    for(node* i=x;i!=nullptr;i = i->pa) tmp.push_back(i);
    for(int i=(int)tmp.size()-1;i>=0;--i) push(tmp[i]);
}
int find_id(node *x){
    push_path(x);
    int res = size(x->ls)+1;
    while(x->pa != nullptr){
        node *nw = x->pa;
        if(nw->rs == x) res += size(nw->ls)+1;
        x = nw;
    }
    return res;
}
```

## 數學

### 模m下的高斯消去法

```cpp    
LL n,m,v[105][105];

LL power(LL x,LL y,LL md){
    LL res  = 1;
    while(y){
        if(y&1) res = res*x%md;
        x = x*x%md;
        y >>= 1;
    }
    return res;
}

inline void oper(int a,int b,LL c){
    for(int i=1;i<=n+1;++i) v[b][i] = ((v[b][i]+v[a][i]*c)%m+m)%m;
}
void GE(){
    for(int i=1;i<n;++i){
        if(v[i][i] == 0){
            int id = -1;
            for(int j=i+1;j<=n;++j){
                if(v[j][i] != 0){
                    id = j;
                    break;
                }
            }
            if(id != -1) oper(id,i,1);
            else continue;
        }
        for(int j=i+1;j<=n;++j){
            if(v[j][i] == 0) continue;
            LL tmp = -power(v[i][i],m-2,m);
            tmp *= v[j][i];
            oper(i,j,tmp);
        }
    }
    for(int i=n;i>1;--i){
        if(v[i][i] == 0){
            int id = -1;
            for(int j=i-1;j>=1;--j){
                if(v[j][i] != 0){
                    id = j;
                    break;
                }
            }
            if(id != -1) oper(id,i,1);
            else continue;
        }
        for(int j=i-1;j>=1;--j){
            if(v[j][i] == 0) continue;
            LL tmp = -power(v[i][i],m-2,m);
            tmp *= v[j][i];
            oper(i,j,tmp);
        }
    }
}
```

### 擴展歐基里德

```cpp
pair<int,int> exgcd(int a,int b){
    if(b==0) return {1,0};
    pair<int,int> res = exgcd(b,a%b);
    int x = res.first%mod, y = res.second%mod;
    return {y,x-(a/b)*y%mod};
}
int findmi(int a, int mod) { 
    pair<int, int> res = exgcd(a, mod);
    return (result.first%mod+mod)%mod;
}
```
### 中國剩餘定理
![image](https://hackmd.io/_uploads/HJBIYUEN1g.png)
$p[i].first$ $:$ $a_i$
$p[i].second$ $:$ $n_i$
res : x
```cpp
vector<pair<int,int>> p; 
int N = 1, res = 0;
for(auto i:p) N *= i.second;
for(auto i:p){
    int tmp = N/i.second;
    int mi = findmi(tmp,i.second);
    res = (res + i.first*tmp%N*mi%N)%N;
}
```

### 約瑟夫問題 O(n)求存活人
```cpp
int js(int a,int b){ // a人一圈 數b人淘汰 
    if(a==1) return 0;
    return (js(a-1,b)+b)%a;
}
```

### Miller Rabin 質數判定法

```cpp
vector<LL> p = {2,3,5,7,11,13,17};

inline LL lb(LL a){
    return a&(-a);
}
LL power(__int128 x,LL y,LL mod){
    __int128 res = 1;
    x = x%mod;
    while(y){
        if(y&1) res = res*x%mod;
        x = x*x%mod;
        y >>= 1;
    }
    return res;
}
inline bool Miller_Rabin(LL n){
    if(n <= 17){
        if(*lower_bound(p.begin(),p.end(),n) == n) return 1;
        return 0;
    }
    LL s = __lg(lb(n-1));
    LL d = (n-1)/lb(n-1);
    for(LL a:p){
        auto check = [&]() -> bool{
            LL x = power(a,d,n);
            if(x == 1 || x == n-1) return 1;
            for(int i=1;i<s;++i){
                x = (__int128)x*x%n;
                if(x == n-1) return 1;
            }
            return 0;
        };
        if(!check()) return 0;
    }
    return 1;
}
```

### floor_sum

$calculate   \;\;\; \mathrm{floor\_sum}(n,m,a,b) = \sum_{i=1}^{n} \lfloor \frac{ai+b}{m} \rfloor \;\; in \;\; O(logV)$ 

```cpp
LL floor(LL a,LL b){
    if(a>=0 && b>=0 || (a<=0 && b<=0) || (a%b==0)) return a/b;
    return a/b-1;
}
LL floor_sum(LL n,LL m,LL a,LL b){
    LL qa = (floor(a,m)%mod+mod)%mod, qb = (floor(b,m)%mod+mod)%mod;
    LL res = (((n*(n+1)/2LL)%mod*qa%mod + n*qb%mod)%mod+mod)%mod;
    a -= floor(a,m)*m;
    b -= floor(b,m)*m;
    if(n==0 || a==0) return res;
    return ((res + ((a*n+b)/m)*n%mod - floor_sum((a*n+b)/m,a,m,-b-1))%mod+mod)%mod;
}
```
### phi

```cpp
LL phi(LL d){
    LL res = d;
    for(LL p=2;p*p<=d;++p){
        if(d%p == 0){
            while(d%p == 0) d /= p;
            res = res-res/p;
        }
    }
    if(d > 1) res = res-res/d;
    return res;
}
```
### 卡特蘭數


### 生成函數

## 字串

### Manacher's Algorithm
```cpp
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define inf 1e18
#define maxn 2000006
#define endl '\n'

string s,t;
int n,R[maxn],m,T[maxn];

inline int cal(int l,int r){
    int tmp = 0;
    while(l-tmp >= 0 && r+tmp<m && t[l-tmp] == t[r+tmp]) tmp++;
    return tmp;
}
main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>s;
    n = s.size();
    m = n*2+1;
    t.resize(m);
    for(int i=0;i<m;++i){
        if(i&1) t[i] = s[i/2];
        else t[i] = '.';
    }
    int mx = -1,center=-1;
    for(int i=0;i<m;++i){
        if(i > mx){
            R[i] = cal(i,i);
            mx = i+R[i]-1;
            center = i;
        }else{
            int len = mx-i+1;
            int j = center-(i-center);
            if(R[j] == len){
                R[i] = R[j]+cal(i-len,i+len);
                if(i+R[i]-1 > mx){
                    mx = i+R[i]-1;
                    center = i;
                }
            }else if(R[j] < len) R[i] = R[j];
            else R[i] = len;
        }
    }
    int as = 0;
    for(int i=0;i<m;++i){
        as = max(as,R[i]);
    }
    for(int i=0;i<m;++i){
        if(R[i] == as){
            for(int j=i-R[i]+1;j<=i+R[i]-1;++j) if(t[j] != '.') cout<<t[j];
            cout<<endl;
            return 0;
        }
    }
}


```
### Z-algorithm

```cpp
void build_z(string p){
    int len = p.size();
    int L = 0, R = 0;
    z[0] = len;
    for(int i=1;i<len;++i){
        if(i > R || z[i-L] >= R-i+1){
            if(i>R) z[i] = 0;
            else z[i] = R-i+1;
            while(z[i]+i<=len && p[i+z[i]] == p[z[i]]) z[i]++;
            if(z[i]){
                L = i;
                R = i+z[i]-1;
            }
        }else z[i] = z[i-L];
    }
}
```
### KMP
```cpp
int nxt[maxn];
void build(string p){
    int len = p.size(); p = ' '+p;
    int k = 0;
    nxt[1] = 0;
    for(int i=2;i<=len;++i){
        while(k>0 && p[k+1] != p[i]) k = nxt[k];
        if(p[k+1] == p[i]) k++;
        nxt[i] = k;
    }
}
int query(string s,string p){
    int sz = s.size(), pz = p.size(), it = 0, cnt = 0;
    s = ' '+s; p = ' '+p;
    for(int i=1;i<=sz;++i){
        while(it > 0 && p[it+1] != s[i]) it = nxt[it];
        if(p[it+1] == s[i]) it++;
        if(it == pz){
            cnt++;
            it = nxt[it];
        }
    }
    return cnt;
}
```

### Suffix Array 、 LCP Array
```cpp
void c_sort(vector<int> &sa,vector<int> &ra,int k){
    int n = sa.size();
    vector<int> cnt(max((int)260,n)), tmpsa(n);
    for(int i=0;i<n;++i){
        cnt[(i+k<n? ra[i+k]+1:0)]++;
    }
    for(int i=1;i<cnt.size();++i) cnt[i] += cnt[i-1];
    for(int i=n-1;i>=0;--i){
        int tmp = sa[i]+k<n ? ra[sa[i]+k]+1 : 0;
        tmpsa[--cnt[tmp]] = sa[i];
    }
    sa = tmpsa;
}
pair<vector<int>,vector<int>> build_sfx(string &s){
    int n = s.size();
    vector<int> ra(n),sa(n),tmpra(n);
    for(int i=0;i<n;++i){
        sa[i] = i;
        ra[i] = s[i];
    }
    sort(sa.begin(),sa.end(),[&](int a,int b){return s[b] > s[a];});

    for(int k=1;k<n;k<<=1){
        auto comp = [&](int a,int b){
            if(ra[a] != ra[b]) return ra[b] > ra[a];
            int aa = a+k<n ? ra[a+k] : -1;
            int bb = b+k<n ? ra[b+k] : -1;
            return bb > aa;
        };
        c_sort(sa,ra,k);
        c_sort(sa,ra,0);
        tmpra[sa[0]] = 0;
        for(int i=1;i<n;++i){
            tmpra[sa[i]] = tmpra[sa[i-1]];
            if(comp(sa[i-1],sa[i])){
                tmpra[sa[i]]++;
            }
        }
        ra = tmpra;
        if(ra[sa[n-1]] == n-1) break;
    }
    return {sa,ra};
    int k = 0;
}
vector<int> build_lcp(vector<int> &sa,vector<int> &ra,string &s){
    int n = s.size(),k = 0;
    vector<int> lcp(n);
    for(int i=0;i<n;++i){
        int tmp = ra[i];
        if(tmp == 0) continue;
        int j = sa[ra[i]-1];
        while(i+k<n && j+k<n && s[i+k] == s[j+k]) k++;
        lcp[tmp] = k;
        if(k > 0) k--;
    }
    return lcp;
}
```
## 計算幾何

### 基礎模板
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e18
#define maxn 200005
#define endl '\n'
#define X first
#define Y second
typedef pair<int,int> pl;
pl operator+(const pl&a,const pl&b){
    return pl(a.X+b.X,a.Y+b.Y);
}
pl operator-(const pl&a,const pl&b){
    return pl(a.X-b.X,a.Y-b.Y);
}
int operator*(const pl&a,const pl&b){
    return a.X*b.X+a.Y*b.Y;
}
int operator^(const pl&a,const pl&b){
    return a.X*b.Y-a.Y*b.X;
}
int sing(int a){
    return a==0 ? 0 : a>0 ? 1:-1;
}
int ori(pl a,pl b,pl c){
    return sing((b-a)^(c-a));
}
```
### 線段香蕉
```cpp
int btw(pl a,pl b,pl c){
    return ori(a,b,c)==0 && (b-a)*(c-a) <= 0;
}
bool cross(pl a1,pl a2,pl b1,pl b2){
    if(btw(a1,b1,b2) || btw(a2,b1,b2) || btw(b1,a1,a2) || btw(b2,a1,a2)) return true;
    return ori(a1,a2,b1)!=ori(a1,a2,b2) && ori(b1,b2,a1)!=ori(b1,b2,a2);
}
```
### 凸包
```cpp
int n;
pl p[maxn];
vector<pl> convex_hull(){
    sort(p+1,p+1+n);
    vector<pl> Q;
    for(int t=0;t<2;++t){
        int sz = Q.size();
        for(int i=1;i<=n;++i){
            while((int)Q.size()-sz >= 2 && ori(Q.end()[-2],Q.end()[-1],p[i]) == -1)
                Q.pop_back();
            Q.push_back(p[i]);
        }
        Q.pop_back();
        reverse(p+1,p+1+n);
    }
    return Q;
}
```

### 計算 $\angle{bac}$ 度數
```cpp
inline double cal_angle(pl a,pl b,pl c){
    pl v1 = (b-a), v2 = (c-a), v3 = (b-c);
    return acos((v1*v1+v2*v2-v3*v3)/(2.*sqrt(v1*v1)*sqrt(v2*v2)))*(180./M_PI);
}
```

### 最小包覆圓 (隨機)

```cpp!
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define inf 1e18
#define maxn 200005
#define endl '\n'
#define X first
#define Y second
#define double long double
mt19937 rng(243243);
typedef pair<double,double> pl;
struct Line{
    pl o,v;
};
struct circle{
    pl o;
    double r;
};
int n;
pl p[maxn];
pl operator+(const pl&a,const pl&b){
    return pl(a.X+b.X,a.Y+b.Y);
}
pl operator-(const pl&a,const pl&b){
    return pl(a.X-b.X,a.Y-b.Y);
}
double operator*(const pl&a,const pl&b){
    return a.X*b.X+a.Y*b.Y;
}
pl operator*(double a,const pl&b){
    return pl(b.X*a,b.Y*a);
}
double operator^(const pl&a,const pl&b){
    return a.X*b.Y-a.Y*b.X;
}
double dis(const pl&a,const pl&b){
    return sqrt((a-b)*(a-b));
}
Line mid_line(const pl&a,const pl&b){
    return {{(a.X+b.X)/2.,(a.Y+b.Y)/2.},{(b-a).Y,-(b-a).X}};
}
pl inter(const Line &a,const Line&b){
    double tmp = ((b.o-a.o)^b.v)/(a.v^b.v);
    return {a.o+tmp*a.v};
}
circle circum(pl a,pl b,pl c){
    pl o = inter(mid_line(a,b),mid_line(a,c));
    return {o,dis(o,a)};
}

main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    cout<<fixed<<setprecision(17);
    for(int i=1;i<=n;++i) cin>>p[i].X>>p[i].Y;
    shuffle(p+1,p+1+n,rng);
    circle C = {{0,0},0};

    auto check = [&](const pl a) -> bool{
        if(dis(C.o,a) > C.r) return 0;
        return 1;
    };
    for(int i=1;i<=n;++i){
        if(check(p[i])) continue;
        C = {p[i],0};
        for(int j=1;j<i;++j){
            if(check(p[j])) continue;
            C = {0.5*(p[i]+p[j]),dis(p[i],p[j])/2.};
            for(int k=1;k<j;++k){
                if(check(p[k])) continue;
                C = circum(p[i],p[j],p[k]);
            }
        }
    }
    cout<<C.r<<endl;
    cout<<C.o.X<<' '<<C.o.Y<<endl;
}

```

## 其他


### 莫隊
```cpp
bool comp(const qus &a,const qus &b){
    if(a.x/D != b.x/D) return b.x/D > a.x/D;
    return (a.x/D)&1 ? a.y < b.y : b.y < a.y;
}
void add(int id){
    // add arr[id]
}
void ers(int id){
    // erase arr[id]
}
main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    D = n/sqrt(q)+1;
    for(int i=1;i<=n;++i) cin>>arr[i];
    for(int i=1;i<=q;++i){
        cin>>p[i].l>>p[i].r;
        p[i].id = i;
    }
    sort(p+1,p+1+q,comp);
    int l = 1,r = 0;
    for(int i=1;i<=q;++i){
        while(r < p[i].r) add(++r);
        while(l > p[i].l) add(--l);
        while(r > p[i].r) ers(r--);
        while(l < p[i].l) ers(l++);
        as[p[i].id] = res;
    }
    for(int i=1;i<=q;++i) cout<<as[i]<<endl;
}
```

### 字典序二分搜
```cpp
int lb(vector<int> &x,vector<vector<int>> &t){
    int l = -1, r = t.size(),mid;
    while(l+1<r){
        mid = (l+r)/2;
        if(t[mid] >= x) r = mid;
        else l = mid;
    }
    return r;
}
int ub(vector<int> &x,vector<vector<int>> &t){
    int l = -1, r = t.size(),mid;
    while(l+1<r){
        mid = (l+r)/2;
        if(t[mid] > x) r = mid;
        else l = mid;
    }
    return r;
}
```

### 枚舉子集S中的子集T

```cpp
    for(int S = 0;S < (1<<n);++S)
        for(int T = S;T; T = (T-1) & S)
```

### 編譯優化
```cpp
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma comment(linker, "/stack:200000000")

```

### Gray Code
```cpp
int n,p[maxn];
main(){
    cin>>n;
    for(int i=0;i<(1<<n);++i){
        p[__builtin_ctz(i)] ^= 1;
        for(int j=0;j<n;++j) cout<<p[j];
        cout<<endl;
    }
}
```
### 動態第t小
```cpp
multiset<int> Q1,Q2;
inline void add(int x){
    if(Q1.size() >= t) Q2.insert(x);
    else Q1.insert(x);
    if(!Q1.empty() && !Q2.empty() && *Q2.begin() < *Q1.rbegin()){
        int tmpa = *Q1.rbegin(), tmpb = *Q2.begin();
        Q1.erase(Q1.find(tmpa));
        Q2.erase(Q2.find(tmpb));
        Q2.insert(tmpa);
        Q1.insert(tmpb);
    }
}
inline void ers(int x){
    if(Q2.count(x)){
        Q2.erase(Q2.find(x));
    }else{
        Q1.erase(Q1.find(x));
        Q1.insert(*Q2.begin());
        Q2.erase(Q2.begin());
    }
}
```

### encoding&decoding permutation
```cpp
const int dignum = 45;
string permutation_encode(vector<int> p){
    int n = 16;
    vector<int> cnt(n);
    vector<LL> fac(n+2);
    fac[0] = 1;
    for(int i=1;i<=n;++i) fac[i] = fac[i-1]*(i);
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j) if(p[j] < p[i]) cnt[i]++;
    }
    LL res = 0;
    for(int i=0;i<n;++i){
        res += cnt[i]*fac[(n-(i+1))];
    }
    bitset<dignum> bt = res;
    string s;
    for(int i=0;i<dignum;++i){
        if(bt[i]) s.push_back('1');
        else s.push_back('0');
    }
    return s;
}
vector<int> permutation_decode(string s){
    LL x = 0,tmp = 1;
    int m = dignum, n = 16;
    vector<LL> fac(n+2),p(n);
    fac[0] = 1;
    for(int i=1;i<=n;++i) fac[i] = fac[i-1]*i;
    for(int i=0;i<m;++i){
        if(s[i] == '1') x += tmp;
        tmp <<= 1;
    }
    for(int i=0;i<n;++i){
        LL tmp = fac[n-(i+1)];
        while(x-tmp >= 0){
            p[i]++;
            x -= tmp;
        }
    }
    vector<int> num,res;
    for(int i=0;i<n;++i) num.push_back(i);
    int it = 0;
    while(!num.empty()){
        int idx = p[it++];
        res.push_back(num[idx]);
        num.erase(num.begin()+idx);
    }
    return res;
}
```


# 競賽筆記

## 套路
### 問題轉換
區間修改 -> 差分 ->圖論 (條件傳換)
ex: https://atcoder.jp/contests/typical90/tasks/typical90_aw

其怪的圖論問題(特殊條件，特殊距離定義) -> 建新圖、虛點
ex:
https://atcoder.jp/contests/arc061/tasks/arc061_c
https://atcoder.jp/contests/typical90/tasks/typical90_bj (逆向思考)

位元有關問題 -> 獨立考慮
https://atcoder.jp/contests/typical90/tasks/typi

最短路
https://atcoder.jp/contests/abc216/tasks/abc216_g
https://atcoder.jp/contests/abc404/tasks/abc404_g (差分約束)
![image](https://hackmd.io/_uploads/rk9yxYAi1x.png)

![image](https://hackmd.io/_uploads/HywPvoRiyg.png)



## 數學
![image](https://hackmd.io/_uploads/SyTB5SmPxx.png)

![image](https://hackmd.io/_uploads/By8JHVm5kg.png)

![image](https://hackmd.io/_uploads/Sk4CRPJeex.png)

![image](https://hackmd.io/_uploads/H1pG6KoUgg.png)



錢幣問題：
對於面額 $a,b$ ,符合 $gcd(a,b)=1$
令 $f=ab-a-b$
則對於 $w>f$ 皆可以用兩種面額組出，$w=f$不可組出，$w < f$ 用dp

組合問題不用模又要算C時，可以建帕斯卡三角形

令 f(i,j) 為從 (0,0)走到 (i,j) 的方法數(只能往下或右走)
 it holds that f(r + 1, c) = f(r, 0) + f(r, 1) + ... + f(r, c)

令 $p_n$ 為第n個質數 : 
$p_n \sim n\log n$ (皆為自然對數)
![image](https://hackmd.io/_uploads/BJ55PzjIle.png)
![image](https://hackmd.io/_uploads/BkFRS7j8gl.png)




## 圖論
![image](https://hackmd.io/_uploads/SJKe0LY6yg.png)

### 最大反鍊 = 最小路徑覆蓋 (路徑可重疊)

### 最小路徑覆蓋 (路徑可交疊)求法:
對於每一個(x,y) 符合 x 有一條路徑可已走到 y ，在二分圖中建邊 L[x]->R[y]
求最大匹配

### 最小路徑覆蓋 (路徑不可交疊)求法:
對於每一個(x,y) 符合 x 有一邊直接連到 y ，在二分圖中建邊 L[x]->R[y]
求最大匹配

### 數數
簡單圖單點開始的簡單路徑數量:bit mask dp + 限制初始條件

### 其他
網格圖都是二分圖

## 小技巧
有相同數字時，可以加上第二維資訊 (A[i],i)



