yinyanghu

typedef int F;
#define MAXE 50000
#define MAXV 20000
#define F_INF 1000000

struct MaxFlow {
    int V, E;
    int start[MAXV], next[MAXE], v[MAXE];
    int used[MAXV], level[MAXV];
    F cap[MAXE], flow[MAXE];

yinyanghu

bool extendpath(int x) {
    for (int i = 1; i <= m; ++ i)
        if (edge[x][i] && flag[i]) {
            flag[i] = false;
            if (matching[i] == -1 || extendpath(matching[i])) {
                matching[i] = x;
                return true;
            }
        }
    return false;

yinyanghu

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

const int N = 100000;
const int M = 5000;
const int MOD = 100000000;

int A[N];

yinyanghu

#define MAXST   100000
#define LogMAXST    18

inline int clz(int x){return __builtin_clz(x);}
inline int lg2(int x){return !x ? -1 : 31 - clz(x);}

struct SparseTable {
    int N;
    int F[LogMAXST][MAXST];

yinyanghu

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN    1000 + 1
#define MAXE    2*(MAXN)

yinyanghu

// return x^y mod p
int repeated_squaring(int x, int y, int p) {
    if (y <= 0) return 1;
    int ret = 1;
    for (int base = x; y; base = (base * base) % p, y >>= 1)
        if ((y & 1) == 1) ret = (ret * base) % p;
    return ret;
}

yinyanghu

// return <gcd(a, b), <x, y>> such that ax + by = gcd(a, b)
pair< int, pair<int, int> > extended_euclidean(int a, int b) {
    if (b == 0) return make_pair(a, make_pair(1, 0));
    pair< int, pair<int, int> > next = extended_euclidean(b, a % b);
    int y = next.second.first, x = next.second.second;
    y = y - (a / b) * x;
    return make_pair(next.first, make_pair(x, y));
} 

// p is prime, return b such that a * b = 1 (mod p)

yinyanghu

#define MAXU    100000

struct UnionFind {
    int f[MAXU];
    int rank[MAXU];

    void clear() {
        memset(f, -1, sizeof(f));
        memset(rank, 0, sizeof(rank));
    }

yinyanghu

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN    1000+1
#define INF     100000000

int N;

yinyanghu

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define MAXN    1000+1
#define MAXE    2*10000