不打CF的时候还是不要拷的好
总板子
#include <bits/stdc++.h>
using namespace std;
#define oo 0x3f3f3f3f
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define FO(i,a,b) for (int i=(a);i<=(b);++i)
#define FD(i,a,b) for (int i=(a);i>=(b);--i)
#define FE(i,G,x) for(int i=(G).h[x];~i;i=(G).v[i].nxt)
typedef long long LL;
typedef pair<int, int> PII;
template <class T> inline bool chkmin(T& x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T& x, T y) { return x < y ? x = y, true : false; }
inline LL read(void) {
LL x, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
return x * f;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
return 0;
}
POJ Headers
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <string>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cctype>
#include <climits>
#include <complex>
#include <cstring>
#include <utility>
#include <fstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
Codeforces Time Killer
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
快速乘/快速幂
inline LL mmul(LL a, LL b) {
LL lf = a * ( b >> 25LL ) % MO * ( 1LL << 25 ) % MO ;
LL rg = a * ( b & ( ( 1LL << 25 ) - 1 ) ) % MO ;
return ( lf + rg ) % MO ;
}
inline LL ppow(LL a, LL b) {
LL ret = 1;
for (; b; b >>= 1) {
if (b & 1) ret = ret * a % MO;
a = a * a % MO;
}
return ret;
}
链式前向星
template<typename T, size_t n, size_t m>
struct Graph {
struct { int to, nxt; T w; } v[m];
int h[n], cnt;
Graph() { memset(h, -1, sizeof(h)); }
void clear(){ cnt = 0; memset(h, -1, sizeof(h)); }
void add(int x, int y, const T& w) { v[cnt] = {y, h[x], w}; h[x] = cnt++; }
};
倍增LCA
void pre(int x, int fa) {
anc[0][x] = fa; dep[x] = dep[fa] + 1;
FO(i, 1, 18) anc[i][x] = anc[i - 1][anc[i - 1][x]];
FE(i, G, x) {
int to = G.v[i].to;
if (to != fa) pre(to, x);
}
}
int lca(int x, int y) {
if (dep[x] > dep[y]) swap(x, y);
int d = dep[y] - dep[x];
FD(i, 18, 0) if ((d >> i) & 1) y = anc[i][y];
if (x == y) return x;
FD(i, 18, 0) if (anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];
return anc[0][x];
}
Treap
namespace Treap {
struct node {
node* ls, *rs;
int pri, key, size;
void upd() { size = 1 + (ls ? ls->size : 0) + (rs ? rs->size : 0); }
node() { ls = rs = NULL; }
}* root;
typedef pair<node*, node*> decr;
inline int ran() {
static int x = 23333;
return x ^= x << 13, x ^= x>>17, x ^= x << 5;
}
inline int size(node* x) { return x ? x->size : 0; }
node* merge(node* x, node* y) {
if (!(x && y)) return x ? x : y;
if (x->pri < y->pri) {
x->rs = merge(x->rs, y); x->upd();
return x;
} else {
y->ls = merge(x, y->ls); y->upd();
return y;
}
}
decr split(node* x, int n) {
if (!x) return decr(NULL, NULL);
decr ret;
if (size(x->ls) >= n) {
ret = split(x->ls, n);
x->ls = ret.se; x->upd();
ret.se = x;
} else {
ret = split(x->rs, n - size(x->ls) - 1);
x->rs = ret.fi; x->upd();
ret.fi = x;
}
return ret;
}
inline int findkth(int k) {
decr x = split(root, k - 1);
decr y = split(x.se, 1);
int ans = y.fi->key;
root = merge(merge(x.fi, y.fi), y.se);
return ans;
}
int getkth(node* x, int y) {
if (!x) return 0;
return (y < x->key) ? getkth(x->ls, y) : getkth(x->rs, y) + size(x->ls) + 1;
}
inline void ins(int x) {
node* t = new node;
t->pri = ran(); t->key = x; t->size = 1;
int k = getkth(root, x);
decr p = split(root, k);
root = merge(merge(p.fi, t), p.se);
}
inline void del(int x) {
int k = getkth(root, x);
decr p = split(root, k - 1);
decr q = split(p.se, 1);
root = merge(p.fi, q.se);
}
}
矩阵
struct Matrix {
#ifndef MO
#define MO oo
#define REDUCE(x) ;
#endif
enum { maxn = 2 };
int data[maxn + 1][maxn + 1];
Matrix& clear() { memset(data, 0, sizeof(data)); return *this; }
Matrix& unit()
{ clear(); FO(i, 1, maxn) data[i][i] = 1; return *this; }
Matrix operator *(const Matrix& o) {
Matrix ret;
FO(i, 1, maxn) FO(j, 1, maxn) {
ret.data[i][j] = 0;
FO(z, 1, maxn) {
ret.data[i][j] += 1ll * data[i][z] * o.data[z][j] % MO;
REDUCE(ret.data[i][j]);
}
}
return ret;
}
Matrix operator ^(LL x) {
Matrix ret = *this;
if (--x == 0) return ret;
Matrix cnt = *this;
while (x) {
if (x & 1) ret = ret * cnt;
cnt = cnt * cnt;
x >>= 1;
}
return ret;
}
int *operator[](int x){ return data[x]; }
};
Dinic
namespace Dinic {
const int mn = 30005;
const int mm = 1000005;
template<typename T>
struct Graph {
enum { maxn = mn, maxm = mm };
struct Edge {
int to, nxt;
T w, cap, flow;
} v[maxm];
int h[maxn], cur[maxn], cnt;
Graph() { memset(h, -1, sizeof(h)); }
void add1(int x, int y, T w, T cap) {
v[cnt] = Edge{y, h[x], w, cap, 0};
h[x] = cnt++;
}
void add(int x, int y, T w, T cap) {
add1(x, y, w, cap);
add1(y, x, -w, 0);
}
};
Graph<int> G;
int f[mn], Ss, Se;
int dfs(int x, int re) {
if (x == Se || re <= 0) return re;
int s1 = 0, t;
for (int& i = G.cur[x]; i != -1; i = G.v[i].nxt) {
int to = G.v[i].to;
if (f[to] != f[x] + 1) continue;
t = dfs(to, min(re, G.v[i].cap - G.v[i].flow));
G.v[i].flow += t;
G.v[i ^ 1].flow -= t;
s1 += t; re -= t;
if (re == 0) break;
}
return s1;
}
bool bfs() {
memcpy(G.cur, G.h, sizeof(G.h));
queue<int> Q;
memset(f, 0, sizeof(f)); Q.push(Ss); f[Ss] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
FE(i, G, u) {
if (G.v[i].flow >= G.v[i].cap) continue;
int to = G.v[i].to;
if (f[to] != -1) continue;
f[to] = f[u] + 1;
if (to == Se) return 1;
Q.push(to);
}
}
return f[Se] != -1;
}
int MF() {
int ans = 0;
while (bfs()) ans += dfs(Ss, oo);
return ans;
}
}
EK-MCMF
namespace EK{
const int mn = 30005;
const int mm = 1000005;
template<typename T>
struct Graph {
enum { maxn = mn, maxm = mm };
struct Edge {
int to, nxt;
T w, cap, flow;
} v[maxm];
int h[maxn], cnt;
Graph() { memset(h, -1, sizeof(h)); }
void clear(){ cnt = 0; memset(h, -1, sizeof(h)); }
void add1(int x, int y, T w, T cap) {
v[cnt] = Edge{y, h[x], w, cap, 0};
h[x] = cnt++;
}
void add(int x, int y, T w, T cap) {
add1(x, y, w, cap);
add1(y, x, -w, 0);
}
};
Graph<int> G;
int Ss, Se;
int pre[mn], v[mn], dis[mn];
bool spfa() {
#define CLR(x,y) memset(x, y, sizeof(x))
CLR(pre, -1), CLR(dis, oo), CLR(v, false);
#undef CLR
dis[Ss] = 0; v[Ss] = true;
queue<int> Q;
Q.push(Ss);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = G.h[u]; i != -1; i = G.v[i].nxt) {
if (G.v[i].flow >= G.v[i].cap) continue;
int to = G.v[i].to;
if (dis[to] > dis[u] + G.v[i].w) {
dis[to] = dis[u] + G.v[i].w;
pre[to] = i;
if (!v[to]) {
v[to] = true;
Q.push(to);
}
}
}
v[u] = false;
}
return pre[Se] != -1;
}
int MCMF() {
int cost = 0, flow = 0;
while (spfa()) {
int mm = oo;
for (int i = pre[Se]; i != -1; i = pre[G.v[i ^ 1].to])
chkmin(mm, G.v[i].cap - G.v[i].flow);
for (int i = pre[Se]; i != -1; i = pre[G.v[i ^ 1].to]) {
G.v[i].flow += mm;
G.v[i ^ 1].flow -= mm;
cost += G.v[i].w * mm;
}
}
return cost;
}
}
FFT
namespace FFT {
const double pi = acos(-1);
struct comp {
double a, b;
comp() {}
comp(double _a, double _b): a(_a), b(_b) {}
comp operator + (const comp& o) { return comp(a + o.a, b + o.b); }
comp operator - (const comp& o) { return comp(a - o.a, b - o.b); }
comp operator * (const comp& o) { return comp(a * o.a - b * o.b, a * o.b + b * o.a); }
};
int R[500005], m, L;
void init(int n) {
m = 1; L = 0; while (m <= n) m <<= 1, L++;
FO(i, 0, m - 1) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
}
void fft(comp* a, int x) {
FO(i, 0, m - 1) if (i < R[i]) swap(a[i], a[R[i]]);
for (int s = 2; s <= m; s <<= 1) {
comp w0 = comp(cos(2 * pi / s), x * sin(2 * pi / s));
for (int k = 0; k < m; k += s) {
comp w = comp(1, 0);
FO(j, 0, s / 2 - 1) {
comp t = w * a[k + j + s / 2], u = a[k + j];
a[k + j] = u + t; a[k + j + s / 2] = u - t;
w = w * w0;
}
}
}
if (x == -1) FO(i, 0, m - 1) a[i].a /= m;
}
}
线性筛
namespace sieve {
const int N = 100000;
int cnt, mu[N + 5], p[N + 5], phi[N+5];
bool f[N + 5];
void pre() {
mu[1] = phi[1] = 1; cnt = 0;
fill_n(f + 2, N - 1, 1);
FO(i, 2, N) {
if (f[i]) p[++cnt] = i, mu[i] = -1, phi[i] = i - 1;
FO(j, 1, cnt) {
int z = i * p[j];
if (z > N) break;
f[z] = 0;
if (i % p[j] == 0) {
mu[z] = 0, phi[z] = phi[i] * p[j];
break;
} else mu[z] = -mu[i], phi[z] = phi[i] * (p[j] - 1);
}
}
}
}
Miller Rabin
namespace Miller_Rabin{
const int T = 10;
inline LL mmul(LL a, LL b, LL MO) {
LL lf = a * ( b >> 25LL ) % MO * ( 1LL << 25 ) % MO ;
LL rg = a * ( b & ( ( 1LL << 25 ) - 1 ) ) % MO ;
return ( lf + rg ) % MO ;
}
inline LL ppow(LL a, LL b, LL MO) {
LL ret = 1;
for (; b; b >>= 1) {
if (b & 1) ret = ret * a % MO;
a = a * a % MO;
}
return ret;
}
bool witness(LL a, LL n) {
LL j = 0, t = n - 1;
while (!(t & 1LL)) t >>= 1LL, j++;
LL tmp = ppow(a, t, n), last = tmp;
while (j--) {
tmp = mmul(tmp, tmp, n);
if (tmp == 1LL && last != 1LL && last != n - 1) return 1;
last = tmp;
}
if (tmp == 1LL) return 1;
return 0;
}
bool check(LL n) {
if (n == 2LL) return 1;
if (n <= 1LL || !(n & 1LL)) return 0;
for (int i = 0; i < T; i++) {
LL a = rand() % (n - 1) + 1;
if (!witness(a, n)) return 0;
}
return 1;
}
}
拉格朗日插值
// f[0~k] = f(0~k)
FO(j, 0, k) {
f1 = f2 = 1;
FO(i, 0, k) if (i != j) {
f1 = (LL)f1 * (n - i) % MO;
f2 = (LL)f2 * (j - i) % MO;
}
f1 = (LL)f1 * f[j] % MO;
f1 = (LL)f1 * ppow(f2, MO - 2) % MO;
ans = (ans + f1) % MO;
}