---
# System prepended metadata

title: CSES PLAN III

---

{%hackmd BJrTq20hE %}
# CSES PLAN III
因為我跟 `peienwu` 被揍爛了，於是我們決定寫CSES來增進自己的實力
[peienwu CSES補完計畫](https://hackmd.io/@peienwu/cses#CSES-%E8%A3%9C%E5%AE%8C%E8%A8%88%E7%95%AB)
## 目錄
[CSES PLAN I](https://hackmd.io/@thanksone/CSESPLANI)
- Introductory Problems
- Sorting and Searching
- Dynamic Programming
- Graph Algorithms

[CSES PLAN II](https://hackmd.io/@thanksone/CSESPLANII)
- Range Queries
- Tree Algorithms
- Mathematics
- String Algorithms
- Geometry

[CSES PLAN III](https://hackmd.io/@thanksone/CSESPLANIII)
- Advanced Techniques

[CSES PLAN IV](https://hackmd.io/@thanksone/CSESPLANIV)
- Additional Problems

## Advanced Techniques
### [Meet in the Middle](https://cses.fi/problemset/task/1628)
`折半列舉` `二分搜`
```cpp=
#include <iostream>
#include <array>
#include <unordered_map>
#include <algorithm>
#define int long long
using namespace std;
array<int, 40> T;
array<int, 1 << 20> F, S;
void ju(int s, int t, array<int, 1 << 20> &A){
    for(int i = 0; i < 1 << (t - s); i++){
        for(int j = 0; j < (t - s); j++){
            if(i & (1 << j)){
                A[i] = T[s + j] + A[i ^ (1 << j)];
                break;
            }
        }
    }
}
signed main(){
    int n, x, s, cnt = 0;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> T[i];
    }
    ju(0, n / 2, F);
    ju(n / 2, n, S);
    s = 1 << (n - n / 2);
    sort(S.begin(), S.begin() + s);
    for(int f : F){
        if(f) cnt += upper_bound(S.begin(), S.begin() + s, x - f) - lower_bound(S.begin(), S.begin() + s, x - f);
    }
    cnt += upper_bound(S.begin(), S.begin() + s, x) - lower_bound(S.begin(), S.begin() + s, x);
    cout << cnt;
    return 0;
}
```
### [Hamming Distance](https://cses.fi/problemset/task/2136/)
`壓常`
```cpp=
#include <iostream>
#include <array>
#include <bitset>
using namespace std;
array<int, 20004> S;
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, k, ans = 30;
    char b;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++){
            cin >> b;
            S[i] <<= 1;
            S[i] |= b ^ '0';
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            ans = min(ans, (int)__builtin_popcount(S[i] ^ S[j]));
        }
    }
    cout << ans;
    return 0;
}
```
### [Beautiful Subgrids](https://cses.fi/problemset/task/2137)
`壓常`
```cpp=
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
#define int long long
using namespace std;
array<bitset<3000>, 3000> G;
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, ans = 0, tmp;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> G[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            tmp = (G[i] & G[j]).count();
            ans += tmp * (tmp - 1);
        }
    }
    cout << ans / 2;
    return 0;
}
```
### [Reachable Nodes](https://cses.fi/problemset/task/2138)
`壓常` `Topological Sort`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#pragma target("popcnt")
using namespace std;
array<int, 50004> in;
array<bitset<50004>, 50004> dp;
array<vector<int>, 50004> G;
stack<int> ord;
void topu(int n){
    int u;
    queue<int> Q;
    for(int i = 1; i <= n; i++){
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        for(int v : G[u]){
            in[v]--;
            if(!in[v]) Q.push(v);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        dp[u][u] = 1;
        for(int v : G[u]) dp[u] |= dp[v];
    }
}
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        in[b]++;
    }
    topu(n);
    for(int i = 1; i <= n; i++){
        cout << dp[i].count() << " ";
    }
    return 0;
}
```
### [Reachability Queries](https://cses.fi/problemset/task/2143)
`壓常` `Topological Sort` `SCC`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#pragma target("popcnt")
using namespace std;
int cnt = 0;
bitset<50004> vis;
array<int, 50004> in, scc;
array<vector<int>, 50004> G, R, S;
array<bitset<50004>, 50004> dp;
stack<int> out, ord;
void bfs(int u){
    if(vis[u]) return;
    vis[u] = 1;
    for(int v : R[u]) bfs(v);
    out.push(u);
}
void dfs(int u){
    if(scc[u]) return;
    scc[u] = cnt;
    for(int v : G[u]) dfs(v);
}
void topu(int n){
    int u;
    queue<int> Q;
    for(int i = 1; i <= n; i++){
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        for(int v : S[u]){
            in[v]--;
            if(!in[v]) Q.push(v);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        dp[u][u] = 1;
        for(int v : S[u]) dp[u] |= dp[v];
    }
}
signed main(){
    int n, m, q, a, b, u;
    cin >> n >> m >> q;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        R[b].pb(a);
    }
    for(int i = 1; i <= n; i++){
        bfs(i);
    }
    while(!out.empty()){
        u = out.top();
        out.pop();
        if(!scc[u]) cnt++;
        dfs(u);
    }
    for(int i = 1; i <= n; i++){
        for(int v : G[i]){
            if(scc[v] == scc[i]) continue;
            in[scc[v]]++;
            S[scc[i]].pb(scc[v]);
        }
    }
    topu(cnt);
    while(q--){
        cin >> a >> b;
        cout <<(dp[scc[a]][scc[b]]? "YES\n" : "NO\n");
    }
    return 0;
}
```
### [Cut and Paste](https://cses.fi/problemset/task/2072)
`Treap`
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct treap{
    int pri, s;
    char x;
    treap *lc, *rc;
    treap(char c){
        pri = rand();
        lc = rc = nullptr;
        x = c;
        s = 1;
    }
    void pull(){
        s = (lc? lc->s : 0) + (rc? rc->s : 0) + 1;
    }
};
int size(treap *t){
    return t? t->s : 0;
}
treap* merge(treap *a, treap *b){
    if(!a || !b) return (!a? b : a);
    if(a->pri > b->pri){
        a->rc = merge(a->rc, b);
        a->pull();
        return a;
    }
    else{
        b->lc = merge(a, b->lc);
        b->pull();
        return b;
    }
}
void split(treap *t, treap *&a, treap *&b, int k){
    if(!t){
        a = b = nullptr;
        return;
    }
    if(size(t->lc) + 1 <= k){
        a = t;
        split(t->rc, a->rc, b, k - size(t->lc) - 1);
        a->pull();
    }else{
        b = t;
        split(t->lc, a, b->lc, k);
        b->pull();
    }
}
void print(treap *t){
    if(!t) return;
    print(t->lc);
    cout << t->x;
    print(t->rc);
}
signed main(){
    srand(time(NULL));
    int n, q, l, r;
    char x;
    treap *t = nullptr, *a = nullptr, *b = nullptr, *c = nullptr;
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> x;
        t = merge(t, new treap(x));
    }
    while(q--){
        cin >> l >> r;
        split(t, a, b, l - 1);
        split(b, b, c, r - l + 1);
        t = merge(merge(a, c), b);
    }
    print(t);
    cout << "\n";
    return 0;
}
```
### [Substring Reversals](https://cses.fi/problemset/task/2073)
`Treap`
```cpp=
#include <bits/stdc++.h>
#define np nullptr
using namespace std;
struct treap{
    char x;
    int pri, s;
    bool rev;
    treap *lc, *rc;
    treap(char c){
        pri = rand();
        s = 1;
        x = c;
        rev = 0;
        lc = rc = np;
    }
    void pull(){
        s = (lc? lc->s : 0) + (rc? rc->s : 0) + 1;
    }
    void push(){
        if(!rev) return;
        swap(lc, rc);
        if(lc) lc->rev ^= 1;
        if(rc) rc->rev ^= 1;
        rev = 0;
    }
};
int size(treap *t){
    return t? t->s : 0;
}
treap* merge(treap *a, treap *b){
    if(!a || !b) return a? a : b;
    if(a->pri > b->pri){
        a->push();
        a->rc = merge(a->rc, b);
        a->pull();
        return a;
    }else{
        b->push();
        b->lc = merge(a, b->lc);
        b->pull();
        return b;
    }
}
void split(treap *t, treap *&a, treap *&b, int k){
    if(!t){
        a = b = np;
        return;
    }
    t->push();
    if(k > size(t->lc)){
        a = t;
        split(t->rc, a->rc, b, k - size(t->lc) - 1);
        a->pull();
    }else{
        b = t;
        split(t->lc, a, b->lc, k);
        b->pull();
    }
}
void print(treap *t){
    if(!t) return;
    t->push();
    print(t->lc);
    cout << t->x;
    print(t->rc);
}
signed main(){
    srand(time(NULL));
    int n, q, l, r;
    char x;
    treap *t = np, *a = np, *b = np, *c = np;
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> x;
        t = merge(t, new treap(x));
    }
    while(q--){
        cin >> l >> r;
        split(t, a, b, l - 1);
        split(b, b, c, r - l + 1);
        b->rev ^= 1;
        t = merge(merge(a, b), c);
    }
    print(t);
    cout << "\n";
    return 0;
}
```
### [Reversals and Sums](https://cses.fi/problemset/task/2074)
`Treap`
```cpp=
#include <bits/stdc++.h>
#define int long long
#define np nullptr
using namespace std;
struct treap{
    int x, sum, s, pri;
    bool rev;
    treap *lc, *rc;
    treap(int v){
        x = v;
        sum = x;
        s = 1;
        pri = rand();
        rev = 0;
        lc = rc = np;
    }
    void pull(){
        s = (lc? lc->s : 0) + (rc? rc->s : 0) + 1;
        sum = (lc? lc->sum : 0) + (rc? rc->sum : 0) + x;
    }
    void push(){
        if(!rev) return;
        swap(lc, rc);
        if(lc) lc->rev ^= 1;
        if(rc) rc->rev ^= 1;
        rev = 0;
    }
};
int size(treap *t){
    return t? t->s : 0;
}
treap* merge(treap *a, treap *b){
    if(!a || !b) return a? a : b;
    if(a->pri > b->pri){
        a->push();
        a->rc = merge(a->rc, b);
        a->pull();
        return a;
    }else{
        b->push();
        b->lc = merge(a, b->lc);
        b->pull();
        return b;
    }
}
void split(treap *t, treap *&a, treap *&b, int k){
    if(!t){
        a = b = np;
        return;
    }
    t->push();
    if(k > size(t->lc)){
        a = t;
        split(t->rc, a->rc, b, k - size(t->lc) - 1);
        a->pull();
    }else{
        b = t;
        split(t->lc, a, b->lc, k);
        b->pull();
    }
}
signed main(){
    int n, q, p, l, r, x;
    treap *t = np, *a = np, *b = np, *c = np;
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> x;
        t = merge(t, new treap(x));
    }
    while(q--){
        cin >> p >> l >> r;
        split(t, a, b, l - 1);
        split(b, b, c, r - l + 1);
        if(p == 1) b->rev ^= 1;
        else cout << b->sum << "\n";
        t = merge(merge(a, b), c);
    }
    return 0;
}
```
### [Necessary Roads](https://cses.fi/problemset/task/2076)
`橋` `DFS Tree`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct E{
    int u, v;
};
int cnt = 0;
array<int, 100004> low, P;
array<vector<int>, 100004> G;
vector<E> B;
void dfs(int u, int pre){
    P[u] = low[u] = ++cnt;
    for(int v : G[u]){
        if(v == pre) continue;
        if(P[v]) low[u] = min(low[u], P[v]);
        else{
            dfs(v, u);
            if(low[v] > P[u]) B.pb({u, v});
            low[u] = min(low[u], low[v]);
        }
    }
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    dfs(1, 0);
    cout << B.size() << "\n";
    for(E e : B){
        cout << e.u << " " << e.v << "\n";
    }
    return 0;
}
```
### [Necessary Cities](https://cses.fi/problemset/task/2077)
`膝蓋` `DFS Tree`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int cnt = 0;
array<int, 100004> P, low;
array<vector<int>, 100004> G;
vector<int> knee;
void dfs(int u, int pre){
    int c = 0;
    bool ok = 0;
    P[u] = low[u] = ++cnt;
    for(int v : G[u]){
        if(v == pre) continue;
        if(P[v]) low[u] = min(low[u], P[v]);
        else{
            c++;
            dfs(v, u);
            if(low[v] >= P[u]) ok = 1;
            low[u] = min(low[u], low[v]);
        }
    }
    if((ok && u > 1) || (u == 1 && c > 1)) knee.pb(u); 
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    dfs(1, 0);
    cout << knee.size() << "\n";
    for(int k : knee) cout << k << " ";
    cout << "\n";
    return 0;
}
```
### [Eulerian Subgraphs](https://cses.fi/problemset/task/2078)
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int mod = 1e9 + 7;
int ans = 1;
array<int, 100004> vis;
array<vector<int>, 100004>G;
void dfs(int u, int pre){
    vis[u]++;
    for(int v : G[u]){
        if(v == pre || vis[v] > 1) continue;
        if(vis[v] == 1) ans = ans * 2 % mod;
        else dfs(v, u);
    }
    vis[u]++;
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]) dfs(i, 0);
    }
    cout << ans << "\n";
    return 0;
}
```
### [Monster Game I](https://cses.fi/problemset/task/2084)
`斜率優化`
```cpp=
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
struct line{
    double a, b;
    line(){}
    line(double x, double y): a(x), b(y){}
    double operator*(double x){
        return a * x + b;
    }
    line operator^(line f){
        double x, y;
        x = (b - f.b) / (f.a - a);
        y = f * x;
        return line(x, y);
    }
};
int l, r;
array<double, 200004> F, S, dp;
array<line, 200004> Q;
void pop(double x){
    while(l < r && Q[l] * x > Q[l + 1] * x) l++;
}
void push(line f){
    while(r > l){
        auto [x, y] = f ^ Q[r - 1];
        if(Q[r] * x >= y) r--;
        else break;
    }
    Q[++r] = f;
}
int DP(int n, double x){
    l = 0, r = -1;
    push({x, 0});
    for(int i = 1; i <= n; i++){
        pop(S[i]);
        dp[i] = Q[l] * S[i];
        push({F[i], dp[i]});
    }
    return (int)dp[n];
}
signed main(){
    int n;
    double x;
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> S[i];
    for(int i = 1; i <= n; i++) cin >> F[i];
    cout << DP(n, x) << "\n";
    return 0;
}
```
### [Monster Game II](https://cses.fi/problemset/task/2085/)
`斜率優化` `李超線段樹`
```cpp=
#include <bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
struct line{
    int a, b;
    int operator+(int x){
        return a * x + b;
    }
};
const int inf = 1e6;
array<int, 200004> S, F, dp;
array<line, 4000004> seg;
void update(int p, int l, int r, line s){
    if(s + mid < seg[p] + mid) swap(s, seg[p]);
    if(l == r) return;
    if(s.a > seg[p].a) update(lc, l, mid, s);
    else update(rc, mid + 1, r, s);
}
int query(int p, int l, int r, int x){
    if(l == r) return seg[p] + x;
    if(x <= mid) return min(seg[p] + x, query(lc, l, mid, x));
    else return min(seg[p] + x, query(rc, mid + 1, r, x));
}
int DP(int n){
    update(1, 1, inf, {F[0], 0});
    for(int i = 1; i <= n; i++){
        dp[i] = query(1, 1, inf, S[i]);
        update(1, 1, inf,{F[i], dp[i]});
    }
    return dp[n];
}
signed main(){
    int n, x;
    cin >> n >> x;
    for(int i = 1; i < 4000004; i++) seg[i] = {inf, inf};
    for(int i = 1; i <= n; i++) cin >> S[i];
    for(int i = 1; i <= n; i++) cin >> F[i];
    F[0] = x;
    cout << DP(n) << "\n";
    return 0;
}
```
### [Subarray Squares](https://cses.fi/problemset/task/2086)
`分治優化`
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 3004> X;
array<array<int, 3004>, 3004> dp;
int cost(int l, int r){
    return (X[r] - X[l]) * (X[r] - X[l]);
}
void div(int ql, int qr, int l, int r, int k){
    int t, qm = (ql + qr) >> 1;
    dp[k][qm] = 1e18;
    for(int i = l; i < min(r + 1, qm); i++){
        if(dp[k - 1][i] + cost(i, qm) < dp[k][qm]){
            t = i;
            dp[k][qm] = dp[k - 1][i] + cost(i, qm);
        }
    }
    if(ql == qr) return;
    div(ql, qm, l, t, k);
    div(qm + 1, qr, t, r, k);
}
int DP(int n, int k){
    for(int i = 1; i <= n; i++){
        dp[1][i] = X[i] * X[i];
    }
    for(int i = 2; i <= k; i++){
        div(i, n, i - 1, n, i);
    }
    return dp[k][n];
}
signed main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> X[i];
        X[i] += X[i - 1];
    }
    cout << DP(n, k) << "\n";
    return 0;
}
```
### [Houses and Schools](https://cses.fi/problemset/task/2087)
`分治優化`
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 3004> C;
array<array<int, 3004>, 3004> dis, cst, turn, dp;
void DIS(int n){
    for(int i = 1; i <= n; i++){
        for(int j = i - 1; j > 0; j--){
            dis[i][j] = (i - j) * C[j] + dis[i][j + 1];
        }
        for(int j = i + 1; j <= n; j++){
            dis[i][j] = (j - i) * C[j] + dis[i][j - 1];
        }
    }
    for(int i = 1; i <= n; i++){
        cst[i][i] = 0;
        turn[i][i] = i;
    }
    for(int k = 1; k < n; k++){
        for(int i = 1, j = i + k; j <= n; i++, j++){
            cst[i][j] = 1e18;
            for(int t = turn[i][j - 1]; t <= turn[i + 1][j]; t++){
                if(dis[t][i] + dis[t][j] < cst[i][j]){
                    cst[i][j] = dis[t][i] + dis[t][j];
                    turn[i][j] = t;
                }
            }
        }
    }
}
void div(int ql, int qr, int l, int r, int k){
    int t, qm = (ql + qr) >> 1;
    dp[k][qm] = 1e18;
    for(int i = l; i < min(r + 1, qm); i++){
        if(dp[k][qm] > dp[k - 1][i] + cst[i + 1][qm]){
            dp[k][qm] = dp[k - 1][i] + cst[i + 1][qm];
            t = i;
        }
    }
    if(ql == qr) return;
    div(ql, qm, l, t, k);
    div(qm + 1, qr, t, r, k);
}
int DP(int n, int k){
    for(int i = 1; i <= n; i++){
        dp[1][i] = cst[1][i];
    }
    for(int i = 2; i <= k; i++){
        div(i, n, i - 1, n, i);
    }
    return dp[k][n];
}
signed main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> C[i];
    DIS(n);
    cout << DP(n, k) << "\n";
    return 0;
}
```
### [Knuth Division](https://cses.fi/problemset/task/2088)
`Knuth 優化`
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 5004> X;
array<array<int, 5004>, 5004> dp, turn;
int DP(int n){
    for(int i = 1; i <= n; i++){
        dp[i][i] = 0;
        turn[i][i] = i;
    }
    for(int k = 1; k < n; k++){
        for(int i = 1, j = i + k; j <= n; i++, j++){
            dp[i][j] = 1e18;
            for(int t = turn[i][j - 1]; t <= turn[i + 1][j]; t++){
                if(dp[i][t] + dp[t + 1][j] < dp[i][j]){
                    turn[i][j] = t;
                    dp[i][j] = dp[i][t] + dp[t + 1][j];
                }
            }
            dp[i][j] += X[j] - X[i - 1];
        }
    }
    return dp[1][n];
}
signed main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> X[i];
        X[i] += X[i - 1];
    }
    cout << DP(n) << "\n";
    return 0;
}
```
### [Apples and Bananas](https://cses.fi/problemset/task/2111)
`FFT`
```cpp=
#include <bits/stdc++.h>
#define int long long
#define cmp complex<double>
#define r real
#define i imag
using namespace std;
const int N = 1 << 19;
const double pi = 3.14159265358979323846264;
array<cmp, 1 << 19> A, B, C, X;
cmp ei(double d){
    return {cos(d), sin(d)};
}
void FFT(array<cmp, 1 << 19> &F){
    int n;
    cmp x;
    for(int i = 0, j = 0; i < N; i++){
        if(i > j) swap(F[i], F[j]);
        for(int k = N >> 1; (j ^= k) < k; k >>= 1);
    }
    for(int k = 2; k <= N; k <<= 1){
        n = k >> 1;
        for(int j = 0; j < N; j += k){
            for(int i = j; i < j + n; i++){
                x = X[(i - j) * N / k] * F[i + n];
                F[i + n] = F[i] - x;
                F[i] += x;
            }
        }
    }
}
int rnd(double x){
    double z = (int)x;
    if(x - z >= 0.5) return (int)z + 1;
    else return (int)z;
}
signed main(){
    int k, n, m, x;
    cin >> k >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> x;
        A[x] += 1;
    }
    for(int i = 0; i < m; i++){
        cin >> x;
        B[x] += 1;
    }
    for(int i = 0; i < N; i++){
        X[i] = ei(2 * pi * i / N);
    }
    FFT(A);
    FFT(B);
    for(int i = 0; i < N; i++){
        C[i] = A[i] * B[i];
        X[i] = conj(X[i]);
    }
    FFT(C);
    for(int i = 2; i <= k << 1; i++){
        cout << rnd(C[i].r() / (double)N) << " ";
    }
    cout << "\n";
    return 0;
}
```
### [One Bit Positions](https://cses.fi/problemset/task/2112)
`FFT`
```cpp=
#include <bits/stdc++.h>
#define cmp complex<double>
#define r real
#define i imag
#define int long long
using namespace std;
const int N = 1 << 19;
const double pi = 3.141592653589793238462643383279502884;
array<cmp, 1 << 19> A, B, C, X;
cmp ei(double d){
    return {cos(d), sin(d)};
}
void FFT(array<cmp, 1 << 19> &F){
    int n;
    cmp x;
    for(int i = 0, j = 0; i < N; i++){
        if(i > j) swap(F[i], F[j]);
        for(int k = N >> 1; (j ^= k) < k; k >>= 1);
    }
    for(int k = 2; k <= N; k <<= 1){
        n = k >> 1;
        for(int j = 0; j < N; j += k){
            for(int i = j; i < j + n; i++){
                x = X[(i - j) * N / k] * F[i + n];
                F[i + n] = F[i] - x;
                F[i] += x;
            }
        }
    }
}
int rnd(double x){
    double z = (int)x;
    if(x - z >= 0.5) return (int)z + 1;
    else return (int)z;
}
signed main(){
    int n;
    string S;
    cin >> S;
    n = S.size();
    for(int i = 0; i < n; i++){
        A[i] = S[i] ^ '0';
        B[n - i - 1] = A[i];
    }
    for(int i = 0; i < N; i++){
        X[i] = ei(2 * pi * i / N);
    }
    FFT(A);
    FFT(B);
    for(int i = 0; i < N; i++){
        C[i] = A[i] * B[i];
        X[i] = conj(X[i]);
    }
    FFT(C);
    for(int i = n; i < (n << 1) - 1; i++){
        cout << rnd(C[i].r() / (double)N) << " ";
    }
    cout << "\n";
    return 0;
}
```
### [Signal Processing](https://cses.fi/problemset/task/2113)
`FFT`
```cpp=
#include <bits/stdc++.h>
#define cmp complex<double>
#define r real
#define i imag
#define int long long
using namespace std;
const int N = 1 << 19;
const double pi = 3.14159265358979323846264338327950288419716939937105820974944;
array<cmp, 1 << 19> A, B, C, X;
cmp ei(double d){
    return {cos(d), sin(d)};
}
void FFT(array<cmp, 1 << 19> &F){
    int n;
    cmp x;
    for(int i = 0, j = 0; i < N; i++){
        if(i > j) swap(F[i], F[j]);
        for(int k = N >> 1; (j ^= k) < k; k >>= 1);
    }
    for(int k = 2; k <= N; k <<= 1){
        n = k >> 1;
        for(int j = 0; j < N; j += k){
            for(int i = j; i < j + n; i++){
                x = X[(i - j) * N / k] * F[i + n];
                F[i + n] = F[i] - x;
                F[i] += x;
            }
        }
    }
}
int rnd(double x){
    double z = (int)x;
    if(x - z >= 0.5) return (int)z + 1;
    else return (int)z;
}
signed main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    for(int i = m - 1; i >= 0; i--){
        cin >> B[i];
    }
    for(int i = 0; i < N; i++){
        X[i] = ei(2 * pi * i / N);
    }
    FFT(A);
    FFT(B);
    for(int i = 0; i < N; i++){
        C[i] = A[i] * B[i];
        X[i] = conj(X[i]);
    }
    FFT(C);
    for(int i = 0; i < n + m - 1; i++){
        cout << rnd(C[i].r() / (double)N) << " ";
    }
    cout << "\n";
    return 0;
}
```
### [New Roads Queries](https://cses.fi/problemset/task/2101)
`LCA`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct E{
    int v, t;
};
int cnt = 0;
array<int, 200004> in, out, dsu;
array<array<int, 20>, 200004> A, T;
array<vector<E>, 200004> G;
int find(int u){
    if(dsu[u] == u) return u;
    return dsu[u] = find(dsu[u]);
}
void onion(int a, int b){
    int A = find(a), B = find(b);
    dsu[A] = B;
}
void dfs(int u){
    in[u] = ++cnt;
    for(auto [v, t] : G[u]){
        if(in[v]) continue;
        dfs(v);
        T[v][0] = t;
        A[v][0] = u;
    }
    out[u] = ++cnt;
}
void dabo(int n){
    in[0] = 0, out[0] = 1e9;
    for(int j = 1; j < 18; j++){
        for(int i = 1; i <= n; i++){
            A[i][j] = A[A[i][j - 1]][j - 1];
            T[i][j] = max(T[i][j - 1], T[A[i][j - 1]][j - 1]);
        }
    }
}
int query(int a, int b){
    if(find(a) != find(b)) return -1;
    int ans = 0;
    for(int i = 17; i >= 0; i--){
        if(in[A[a][i]] > in[b] || out[A[a][i]] < out[b]){
            ans = max(ans, T[a][i]);
            a = A[a][i];
        }
    }
    if(in[a] > in[b] || out[a] < out[b]){
        ans = max(ans, T[a][0]);
        a = A[a][0];
    }
    for(int i = 17; i >= 0; i--){
        if(in[A[b][i]] > in[a] || out[A[b][i]] < out[a]){
            ans = max(ans, T[b][i]);
            b = A[b][i];
        }
    }
    if(in[b] > in[a] || out[b] < out[a]){
        ans = max(ans, T[b][0]);
        b = A[b][0];
    }
    return ans;
}
signed main(){
    int n, m, q, a, b;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) dsu[i] = i;
    for(int i = 1; i <= m; i++){
        cin >> a >> b;
        if(find(a) == find(b)) continue;
        G[a].pb({b, i});
        G[b].pb({a, i});
        onion(a, b);
    }
    for(int i = 1; i <= n; i++){
        if(!in[i]) dfs(i);
    }
    dabo(n);
    while(q--){
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
    return 0;
}
```
### [Dynamic Connectivity](https://cses.fi/problemset/task/2133)
`Segment Tree`
```cpp=
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mid ((l + r) >> 1)
using namespace std;
struct edge{
    int u, v, l, r;
};
int n, com;
array<int, 100004> DSU;
vector<pair<int, int>> tmp;
stack<vector<pair<int, int>>> chg;
int ehash(int u, int v){
    return u * 100001 + v;
}
pair<int, int> dehash(int x){
    return {x / 100001, x % 100001};
}
int find(int u){
    tmp.pb({u, DSU[u]});
    if(DSU[u] == u){
        chg.push(tmp);
        tmp.clear();
        return u;
    }
    return DSU[u] = find(DSU[u]);
}
void onion(int u, int v){
    int U = find(u), V = find(v);
    if(U == V) return;
    DSU[V] = U;
    com--;
}
void roll(){
    tmp = chg.top();
    chg.pop();
    for(auto [u, d] : tmp){
        DSU[u] = d;
    }
    tmp.clear();
}
void run(int l, int r, vector<edge> &E){
    int c = com;
    vector<edge> D;
    for(edge e : E){
        if(e.l > r || e.r < l) continue;
        if(e.l <= l && e.r >= r) onion(e.u, e.v);
        else D.pb(e);
    }
    if(l == r) cout << com << " ";
    else{
        run(l, mid, D);
        run(mid + 1, r, D);
    }
    for(edge e : E){
        if(e.l <= l && e.r >= r) roll(), roll();
    }
    com = c;
}
signed main(){
    int m, q, t, a, b, p = 0;
    vector<edge> E;
    map<int, int> M;
    cin >> n >> m >> q;
    com = n;
    for(int i = 1; i <= n; i++) DSU[i] = i;
    while(m--){
        cin >> a >> b;
        if(a > b) swap(a, b);
        M[ehash(a, b)] = 0;
    }
    while(q--){
        cin >> t >> a >> b;
        if(a > b) swap(a, b);
        p++;
        if(t == 1) M[ehash(a, b)] = p;
        else{
            E.pb({a, b, M[ehash(a, b)], p - 1});
            M.erase(ehash(a, b));
        }
    }
    for(auto [e, s] : M){
        auto [u, v] = dehash(e);
        E.pb({u, v, s, p});
    }
    run(0, p, E);
    return 0;
}
```
### [Parcel Delivery](https://cses.fi/problemset/task/2121)
`Min Cost Max Flow`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct pipe{
    int u, v, f, c;
};
int cnt = 0;
bitset<504> vis, in;
array<int, 504> cost, pre;
array<vector<int>, 504> G;
array<pipe, 2004> E;
void add(int u, int v, int f, int c){
    G[u].pb(cnt);
    E[cnt++] = {u, v, f, c};
    G[v].pb(cnt);
    E[cnt++] = {v, u, 0, -c};
}
void run(int u){
    if(u == 1) return;
    pipe &e = E[pre[u]], &b = E[pre[u] ^ 1];
    e.f++;
    b.f--;
    run(e.v);
}
void SPFA(int s){
    int u, v;
    queue<int> Q;
    cost[s] = 0;
    Q.push(s);
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        vis[u] = 1;
        in[u] = 0;
        for(int i : G[u]){
            if(!E[i].f) continue;
            v = E[i].v;
            if(cost[u] + E[i].c < cost[v]){
                pre[v] = i ^ 1;
                cost[v] = cost[u] + E[i].c;
                if(!in[v]){
                    in[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int flow(int n, int k){
    int ans = 0;
    while(k--){
        for(int i = 1; i <= n; i++){
            cost[i] = 1e9;
            vis[i] = 0;
        }
        SPFA(1);
        if(!vis[n]) return -1;
        run(n);
        ans += cost[n];
    }
    return ans;
}
signed main(){
    int n, m, k, a, b, f, c;
    cin >> n >> m >> k;
    while(m--){
        cin >> a >> b >> f >> c;
        add(a, b, f, c);
    }
    cout << flow(n, k) << "\n";
    return 0;
}
```
### [Task Assignment](https://cses.fi/problemset/task/2129)
`Min Cost Max Flow`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct pipe{
    int u, v, f, c;
};
int cnt = 0;
bitset<412> in;
array<int, 412> cost, pre;
array<vector<int>, 412> G;
array<pipe, 81204> E;
void add(int u, int v, int f, int c){
    G[u].pb(cnt);
    E[cnt++] = {u, v, f, c};
    G[v].pb(cnt);
    E[cnt++] = {v, u, 0, -c};
}
void run(int u){
    if(!u) return;
    pipe &e = E[pre[u]], &b = E[pre[u] ^ 1];
    b.f--;
    e.f++;
    run(e.v);
}
void SPFA(int s){
    int u, v;
    queue<int> Q;
    cost[s] = 0;
    Q.push(s);
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        in[u] = 0;
        for(int i : G[u]){
            if(!E[i].f) continue;
            v = E[i].v;
            if(cost[u] + E[i].c < cost[v]){
                cost[v] = cost[u] + E[i].c;
                pre[v] = i ^ 1;
                if(!in[v]){
                    in[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int flow(int n, int k){
    int ans = 0;
    while(k--){
        for(int i = 0; i <= n; i++) cost[i] = 1e9;
        SPFA(0);
        run(n);
        ans += cost[n];
    }
    return ans;
}
signed main(){
    int n, c;
    cin >> n;
    for(int i = 1; i <= n; i++){
        add(0, i, 1, 0);
        add(200 + i, 404, 1, 0);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> c;
            add(i, 200 + j, 1, c);
        }
    }
    cout << flow(404, n) << "\n";
    for(int i = 1; i <= n; i++){
        cout << i << " ";
        for(int j : G[i]){
            if(!E[j].f) cout << E[j].v - 200 << "\n";
        }
    }
    return 0;
}
```
### [Distinct Routes II](https://cses.fi/problemset/task/2130)
`Min Cost Max Flow`
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct pipe{
    int u, v, f, c;
};
int cnt = 0;
bitset<504> vis, in;
array<int, 504> cost, pre;
array<vector<int>, 504> G;
array<pipe, 2004> E;
vector<int> R;
void add(int u, int v, int f, int c){
    G[u].pb(cnt);
    E[cnt++] = {u, v, f, c};
    G[v].pb(cnt);
    E[cnt++] = {v, u, 0, -c};
}
void run(int u){
    if(u == 1) return;
    pipe &e = E[pre[u]], &b = E[pre[u] ^ 1];
    b.f--;
    e.f++;
    run(e.v);
}
void SPFA(int s){
    int u, v;
    queue<int> Q;
    cost[s] = 0;
    Q.push(s);
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        vis[u] = 1;
        in[u] = 0;
        for(int i : G[u]){
            if(!E[i].f) continue;
            v = E[i].v;
            if(cost[u] + E[i].c < cost[v]){
                cost[v] = cost[u] + E[i].c;
                pre[v] = i ^ 1;
                if(!in[v]){
                    in[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int flow(int n, int k){
    int ans = 0;
    while(k--){
        for(int i = 1; i <= n; i++){
            cost[i] = 1e9;
            vis[i] = 0;
        }
        SPFA(1);
        if(!vis[n]) return -1;
        run(n);
        ans += cost[n];
    }
    return ans;
}
void dfs(int u){
    R.pb(u);
    for(int i : G[u]){
        if(i % 2 == 0 && !E[i].f){
            dfs(E[i].v);
            E[i].f++;
            return;
        }
    }
}
signed main(){
    int n, m, k, a, b;
    cin >> n >> m >> k;
    while(m--){
        cin >> a >> b;
        add(a, b, 1, 1);
    }
    cout << flow(n, k) << "\n";
    while(k--){
        R.clear();
        dfs(1);
        cout << R.size() << "\n";
        for(int u : R) cout << u << " ";
        cout << "\n";
    }
    return 0;
}
```
