Template

基本

头文件

  • 普通青年
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cctype>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
  • 文艺青年
1
#include <bits/stdc++.h>
  • 二逼青年
1
2
//#include <cstdio>
#include <windows.h>

$I/O$ 优化

  • 一般读入优化
1
2
3
4
5
6
int read() {
int u = 0; bool f = false; char c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = true;
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}
  • $fread$
1
2
3
4
5
6
7
8
9
10
struct io {
char op[1 << 26], *s;
io() { fread(s = op, 1, 1 << 26, stdin); }
int read(bool f = false, int u = 0) {
while (*s < 48) if (*s++ == '-') f = true;
while (*s > 47) u = (u << 1) + (u << 3) + *s++ - '0';
return f ? -u : u;
}
}ip;
#define read ip.read
  • 一般输出优化
1
2
3
4
5
6
7
char op[20]; int tp;
void write(int u) {
bool f = u < 0; u = f ? -u : u; tp = 0;
for (; u; u /= 10) op[++tp] = u % 10 + '0';
if (f) putchar('-'); if(!tp) putchar('0');
for (;tp; --tp) putchar(op[tp]);
}

离散化

1
2
3
4
5
6
7
8
9
const int maxn = 1e5 + 10; int aux[maxn];
void discretization(int *begin, int *end) {
aux[0] = 0;
for (int *i = begin; i != end; ++i) aux[++aux[0]] = *i;
std::sort(aux + 1, aux + 1 + aux[0]);
aux[0] = std::unique(aux + 1, aux + 1 + aux[0]) - aux - 1;
for (int *i = begin; i != end; ++i)
*i = std::lower_bound(aux + 1, aux + 1 + aux[0], *i) - aux;
}

数据结构

并查集

1
2
3
4
5
6
7
const int maxn = 1e5 + 10;
struct mergefindSet {
int fa[maxn];
void clear(int n) { for (int i = 0; i <= n; i++) fa[i] = i; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
};

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
const int maxn = 1e5 + 10;
struct BIT {
int s[maxn], maxs;
void clear(int n) {
for (int i = 0; i <= n; i++) s[i] = 0; maxs = n;
}
void add(int p, int v) {
for (int i = p; i <= maxs; i += i & -i) s[i] += v;
}
int sum(int p, int v = 0) {
for (int i = p; i; i -= i & -i) v += s[i]; return v;
}
}

线段树

  • 普通线段树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int maxn = 1e5 + 10;
namespace Seg {
ll sum[maxn << 2], tag[maxn << 2];
void pushup(int p) {
sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
void build(int p, int l, int r) {
if (l == r) return (void)(scanf("%lld", &sum[p]));
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
void pushdown(int p, int l, int r) {
if (!tag[p]) return;
int mid = l + r >> 1;
sum[p << 1] += (mid - l + 1) * tag[p];
sum[p << 1 | 1] += (r - mid) * tag[p];
tag[p << 1] += tag[p]; tag[p << 1 | 1] += tag[p];
tag[p] = 0;
}
void add(int p, int l, int r, int lp ,int rp, ll v) {
if (l == lp && r == rp) {
sum[p] += (r - l + 1) * v;
tag[p] += v; return;
}pushdown(p, l, r); int mid = l + r >> 1;
if(rp <= mid) add(p << 1, l, mid, lp, rp, v);
else if(lp > mid) add(p << 1 | 1, mid + 1, r, lp, rp, v);
else add(p << 1, l, mid, lp, mid, v), add(p << 1 | 1, mid + 1, r, mid + 1, rp, v);
pushup(p);
}
ll query(int p, int l, int r, int lp, int rp) {
if (l == lp && r == rp) return sum[p];
pushdown(p, l, r); int mid = l + r >> 1;
if(rp <= mid) return query(p << 1, l, mid, lp, rp);
else if(lp > mid) return query(p << 1 | 1, mid + 1, r, lp, rp);
else return query(p << 1, l, mid, lp, mid) + query(p << 1 | 1, mid + 1, r, mid + 1, rp);
}
}
  • 标记永久化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int maxn = 1e5 + 10;
namespace Seg {
#define ls (p << 1)
#define rs (p << 1 | 1)
ll sum[maxn << 2], all[maxn << 2];
void build(int p, int l, int r) {
if (l == r) return void(sum[p] = read());
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
sum[p] = sum[ls] + sum[rs];
}
void update(int p, int l, int r, int lq, int rq, int val) {
if (l == lq && r == rq)
return void(all[p] += val);
sum[p] += (ll) val * (rq - lq + 1);
int mid = l + r >> 1;
if (rq <= mid) update(ls, l, mid, lq, rq, val);
else if (lq > mid) update(rs, mid + 1, r, lq, rq, val);
else update(ls, l, mid, lq, mid, val), update(rs, mid + 1, r, mid + 1, rq, val);
}
ll query(int p, int l, int r, int lq, int rq) {
ll ans = all[p] * (rq - lq + 1);
if (l == lq && r == rq)
return ans + sum[p];
int mid = l + r >> 1;
if (rq <= mid) return query(ls, l, mid, lq, rq) + ans;
else if (lq > mid) return query(rs, mid + 1, r, lq, rq) + ans;
else return query(ls, l, mid, lq, mid) + query(rs, mid + 1, r, mid + 1, rq) + ans;
}
}

平衡树

  • $fhq~Treap$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
namespace Treap {
#define nl NULL
struct node {
node *son[2];
int _rand, _size, _value;
node(int val) {
son[0] = son[1] = nl;
_rand = rand(); _size = 1;
_value = val;
}
int size() {
return this == nl ? 0 : _size;
}
void maintain() {
_size = son[0]->size() + 1 + son[1]->size();
}
}*root, *a, *b, *c, *d;
node *merge(node *x, node *y) {
if (!x || !y) return x ? x : y;
if (x->_rand < y->_rand) {
x->son[1] = merge(x->son[1], y);
x->maintain(); return x;
}
else {
y->son[0] = merge(x, y->son[0]);
y->maintain(); return y;
}
}
node *merge(node *x, node *y, node *z) {
return merge(merge(x, y), z);
}
void split(node *t, int val, node* &x, node* &y) {
if (!t) return void(x = y = nl);
if (val > t->_value)
x = t, split(t->son[1], val, x->son[1], y);
else
y = t, split(t->son[0], val, x, y->son[0]);
t->maintain();
}
void insert(int val) {
split(root, val, a, b);
root = merge(a, new node(val), b);
}
void erase(int val) {
split(root, val, a, b);
split(b, val + 1, b, c);
d = b;
if (b) b = merge(b->son[0], b->son[1]);
root = merge(a, b, c);
delete d;
}
int kth(int rank) {
for (node *t = root; t;) {
if (rank == t->son[0]->size() + 1) return t->_value;
if (rank <= t->son[0]->size()) t = t->son[0];
else rank -= t->son[0]->size() + 1, t = t->son[1];
}
}
int find(int val) {
split(root, val, a, b);
int r = a->size() + 1;
root = merge(a, b);
return r;
}
int pre(int val) {
int r = 0;
for (node *t = root; t;) {
if (val > t->_value) {
r = t->_value;
t = t->son[1];
}else t = t->son[0];
}return r;
}
int nxt(int val) {
int r = 0;
for (node *t = root; t;) {
if (val < t->_value) {
r = t->_value;
t = t->son[0];
}else t = t->son[1];
}return r;
}
void print() {
printf("#");
for (int i = 1; i <= root->size(); i++)
printf(" %d #", kth(i));
printf("\n");
}
}
  • 可持久化$Treap$(指针版$MLE$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
namespace Treap {
#define nl NULL
struct node {
node *son[2];
int _value, _size, _rand;
node(int val = 0) {
_value = val; _size = 1; _rand = rand();
son[0] = son[1] = nl;
}
int size() {
return this == nl ? 0 : _size;
}
void maintain() {
if (this == nl) return;
_size = son[0]->size() + 1 + son[1]->size();
}
void print() {
if (this == nl) return;
son[0]->print();
printf("%d # ", _value);
son[1]->print();
}
}*a, *b, *c, *d;
std::vector<node*>root(1);
node *copynode(node *t) {
node *p = new node; *p = *t; return p;
}
void split(node *t, int val, node* &x, node* &y) {
if (!t) return void(x = y = nl);
if (t->_value < val)
x = copynode(t), split(t->son[1], val, x->son[1], y);
else
y = copynode(t), split(t->son[0], val, x, y->son[0]);
x->maintain(); y->maintain();
}
node *merge(node *x, node *y) {
if (!x || !y) return x ? x : y;
if (x->_rand < y->_rand) {
node *r = copynode(x);
r->son[1] = merge(r->son[1], y);
r->maintain(); return r;
}
else {
node *r = copynode(y);
r->son[0] = merge(x, r->son[0]);
r->maintain(); return r;
}
}
node *merge(node *x, node *y, node *z) {
return merge(merge(x, y), z);
}
void insert(node *p, int val) {
split(p, val, a, b);
d = new node(val);
c = merge(a, d, b);
root.push_back(c);
//c->print();
}
void erase(node *p, int val) {
split(p, val, a, b);
split(b, val + 1, b, c);
if (b == nl) return root.push_back(p);
b = merge(b->son[0], b->son[1]);
root.push_back(merge(a, b, c));
}
int find(node *p, int val) {
root.push_back(p);
int r = 0;
for (node *t = p; t; ) {
if (t->_value < val) {
r += t->son[0]->size() + 1;
t = t->son[1];
}
else t = t->son[0];
}
return r + 1;
}
int kth(node *p, int rank) {
root.push_back(p);
for (node *t = p; t; ) {
if (t->son[0]->size() + 1 == rank) return t->_value;
if (t->son[0]->size() >= rank) t = t->son[0];
else rank -= t->son[0]->size() + 1, t = t->son[1];
}
}
int pre(node *p, int val) {
root.push_back(p);
int r = -2147483647;
for (node *t = p; t; ) {
if (t->_value < val) {
r = t->_value;
t = t->son[1];
}else t = t->son[0];
}return r;
}
int nxt(node *p, int val) {
root.push_back(p);
int r = 2147483647;
for (node *t = p; t; ) {
if (t->_value > val) {
r = t->_value;
t = t->son[0];
}else t = t->son[1];
}return r;
}
}
  • 可持久化$Treap$(数组板$AC$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
namespace Treap {
const int maxn = 5e5;
struct node {
int son[2], value, size, fix;
node() {}
node(int val = 0, bool e = false) {
fix = rand(); value = val; size = e; son[0] = son[1] = 0;
}
}T[maxn * 50];
int root[maxn], nodeCnt, rootCnt;
int copynode(int p) {
T[++nodeCnt] = T[p]; return nodeCnt;
}
int newnode(int val) {
T[++nodeCnt] = node(val, true); return nodeCnt;
}
void maintain(int p) {
if (p) T[p].size = T[T[p].son[0]].size + T[T[p].son[1]].size + 1;
}
void split(int p, int val, int &x, int &y) {
if (!p) return void(x = y = 0);
if (T[p].value < val)
x = copynode(p), split(T[p].son[1], val, T[x].son[1], y);
else
y = copynode(p), split(T[p].son[0], val, x, T[y].son[0]);
maintain(x); maintain(y);
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (T[x].fix < T[y].fix) {
int r = copynode(x);
T[r].son[1] = merge(T[x].son[1], y);
maintain(r); return r;
}
else {
int r = copynode(y);
T[r].son[0] = merge(x, T[y].son[0]);
maintain(r); return r;
}
}
int merge(int x, int y, int z) {
return merge(merge(x, y), z);
}
void insert(int p, int val) {
int a, b, c;
split(p, val, a, c);
b = newnode(val);
root[++rootCnt] = merge(a, b, c);
}
void erase(int p, int val) {
int a, b, c;
split(p, val, a, b);
split(b, val + 1, b, c);
b = merge(T[b].son[0], T[b].son[1]);
root[++rootCnt] = merge(a, b, c);
}
int find(int p, int val) {
root[++rootCnt] = p;
int r = 0;
while (p) {
if (T[p].value < val)
r += T[T[p].son[0]].size + 1, p = T[p].son[1];
else p = T[p].son[0];
}
return r + 1;
}
int kth(int p, int rank) {
root[++rootCnt] = p;
while (p) {
if (T[T[p].son[0]].size + 1 == rank) return T[p].value;
if (T[T[p].son[0]].size >= rank) p = T[p].son[0];
else rank -= 1 + T[T[p].son[0]].size, p = T[p].son[1];
}
}
int pre(int p, int val) {
root[++rootCnt] = p;
int r = -2147483647;
while (p)
if (T[p].value < val)
r = T[p].value, p = T[p].son[1];
else p = T[p].son[0];
return r;
}
int nxt(int p, int val) {
root[++rootCnt] = p;
int r = 2147483647;
while (p)
if (T[p].value > val)
r = T[p].value, p = T[p].son[0];
else p = T[p].son[1];
return r;
}
}
  • $splay$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
namespace Splay {
#define nl NULL
struct node {
node *father, *son[2];
int _value, _size, _count;
node(int val, node *f = nl) {
_value = val; _size = _count = 1;
father = f; son[0] = son[1] = nl;
}
int size() {
return this == nl ? 0 : _size;
}
bool who() {
return father->son[1] == this;
}
void maintain() {
_size = son[0]->size() + _count + son[1]->size();
}
}*root;
void rotate(node *t) {
node *f = t->father, *g = f->father;
bool a = t->who(), b = !a;
f->son[a] = t->son[b];
if (t->son[b])
t->son[b]->father = f;
t->father = g;
if (g)
g->son[f->who()] = t;
else
root = t;
t->son[b] = f;
f->father = t;
f->maintain();
t->maintain();
}
void splay(node *t, node *p) {
while (t->father != p) {
node *f = t->father;
if (f->father == p) rotate(t);
else if (t->who() ^ f->who())
rotate(t), rotate(t);
else rotate(f), rotate(t);
}
}
void insert(int val) {
if (!root) {
root = new node(val); return;
}
for (node *t = root; t; t = t->son[val > t->_value]) {
if (val == t->_value) {
splay(t, nl); t->_count++;
t->maintain(); return;
}
if (t->son[val > t->_value] == nl) {
bool a = val > t->_value;
t->son[a] = new node(val, t);
splay(t->son[a], nl); return;
}
}
}
void erase(int val) {
node *t = root;
while (t) {
if (t->_value == val) break;
t = t->son[val > t->_value];
}
if (!t) return;
splay(t, nl);
if (t->_count > 1) {
t->_count--; t->_size--; return;
}
if (t->son[0] == nl) {
root = t->son[1];
if (root)
root->father = nl;
delete t; return;
}
node *p = t->son[0];
while (p->son[1])
p = p->son[1];
splay(p, t);
root = p;
p->father = nl;
p->son[1] = t->son[1];
if (t->son[1])
t->son[1]->father = p;
p->maintain(); delete t;
}
int find(int val) {
for (node *t = root; t; t = t->son[val > t->_value])
if (t->_value == val) { splay(t, nl); break; }
return root->son[0]->size() + 1;
}
int kth(int rank) {
for (node *t = root; t;) {
if (t->son[0]->size() < rank && t->son[0]->size() + t->_count >= rank) return t->_value;
if (t->son[0]->size() >= rank) t = t->son[0];
else rank -= t->son[0]->size() + t->_count, t = t->son[1];
}
}
int pre(int val) {
int r = 0;
for (node *t = root; t;) {
if (t->_value < val) {
r = t->_value;
t = t->son[1];
}else t = t->son[0];
}return r;
}
int nxt(int val) {
int r = 0;
for (node *t = root; t;) {
if (t->_value > val) {
r = t->_value;
t = t->son[0];
}else t = t->son[1];
}return r;
}
void print() {
printf("#");
for (int i = 1; i <= root->size(); i++)
printf(" %d #", kth(i));
printf("\n");
}

}

$LinkCut-Tree$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
namespace lct {
struct node {
node *father, *son[2];
int value, sum; bool rev;
node(int val = 0) {
value = val; sum = val; rev = false;
son[0] = son[1] = father = nl;
}
bool is_root() {
if (!father) return true;
return father->son[0] != this && father->son[1] != this;
}
bool who() {
return father->son[1] == this;
}
void reverse() {
swap(son[0], son[1]); rev = !rev;
}
void pushdown_once() {
if (!rev) return; rev = false;
if (son[0]) son[0]->reverse();
if (son[1]) son[1]->reverse();
}
void pushdown() {
if (!is_root()) father->pushdown(); pushdown_once();
}
void maintain() {
sum = value;
if (son[0]) sum += son[0]->sum;
if (son[1]) sum += son[1]->sum;
}
void rotate() {
node *f = father, *g = f->father;
bool a = who(), b = !a;
f->son[a] = son[b];
if (son[b])
son[b]->father = f;
son[b] = f;
father = g;
if (!f->is_root())
g->son[f->who()] = this;
f->father = this;
f->maintain(); maintain();
}
void splay() {
for (pushdown(); !is_root(); rotate())
if (!father->is_root())
if (who() ^ father->who()) rotate();
else father->rotate();
}
void access() {
for (node *y = nl, *x = this; x; y = x, x = x->father)
x->splay(), x->son[1] = y, x->maintain();
}
void make_root() {
access(); splay(); reverse();
}
node *root() {
access(); splay();
for (node *x = this; ; x = x->son[0])
if (!x->son[0]) return x;
}
}*T[maxn];
bool con(int x, int y) {
return T[x]->root() == T[y]->root();
}
void link(int x, int y) {
T[x]->make_root(); T[x]->father = T[y];
}
void cut(int x, int y) {
T[x]->make_root(); T[y]->access(); T[y]->splay();
T[x]->father = T[y]->son[0] = nl; T[y]->maintain();
}
void change(int x, int y) {
T[x]->splay(); T[x]->value = y; T[x]->maintain();
}
int query(int x, int y) {
T[x]->make_root(); T[y]->access();
T[x]->splay(); return T[x]->sum;
}
}

字符串

$hash$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef std::pair<unsigned long long, unsigned long long> pull;
#define A first
#define B second
namespace Hash{
pull Pow[250]; unsigned long long base = 127, Mod1 = 1e9 + 7, Mod2 = 1e9 + 9;
void init(int l) {
Pow[l - 1].A = Pow[l - 1].B = 1;
for (int i = l - 2; i >= 0; --i)
Pow[i].A = Pow[i + 1].A * base % Mod1,
Pow[i].B = Pow[i + 1].B * base % Mod2;
}
pull hash(char *s) {
pull ans(0, 0);
for (int i = 0; s[i]; ++i)
ans.A = (ans.A * base + s[i]) % Mod1,
ans.B = (ans.B * base + s[i]) % Mod2;
return ans;
}
pull hash(pull now, int p, char *s) {
now.A = (now.A + Mod1 - s[p] * Pow[p].A % Mod1) % Mod1;
now.B = (now.B + Mod2 - s[p] * Pow[p].B % Mod2) % Mod2;
return now;
}
}

马拉车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace manacher {
int maxR[maxn];
char t[maxn];
int deal(char *s, int n) {
int m = 0; t[m] = '$'; t[++m] = '#';
for (int i = 0; i < n; i++)
t[++m] = s[i], t[++m] = '#';
t[++m] = '&';
int mid = 0, R = 0;
for (int i = 1; i <= m; i++) {
if (i <= R) maxR[i] = std::min(maxR[mid * 2 - i], R - i);
while (t[i - maxR[i] - 1] == t[i + maxR[i] + 1]) maxR[i]++;
if (i + maxR[i] > R) R = i + maxR[i], mid = i;
}
int ans = 0;
for (int i = 1; i < m; i ++)
ans = Mod(ans + ((maxR[i] + 1) >> 1));
return ans;
}
}

后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace Suffix {
int SA[maxn], Rank[maxn], Height[maxn], str[maxn], tmp[maxn], Tax[maxn];
void init(int n) {
for (int i = 1; i <= n; i++) scanf("%d", &str[i]);
}
void sort(int n, int m) {
for (int i = 0; i <= m; i++) Tax[i] = 0;
for (int i = 1; i <= n; i++) Tax[Rank[i]]++;
for (int i = 1; i <= m; i++) Tax[i] += Tax[i - 1];
for (int i = n; i; i--) SA[Tax[Rank[tmp[i]]]--] = tmp[i];
}
bool cmp(int *f, int x, int y, int w, int n) {
return f[x] == f[y] && (x + w > n ? 0 : f[x + w]) == (y + w > n ? 0 : f[y + w]);
}
void build(int n) {
init(n);
for (int i = 1; i <= n; i++) Rank[i] = str[i], tmp[i] = i;
int m = 1000; sort(n, m);
for (int i, w = 1, p = 1; p < n; m = p, w <<= 1) {
for (p = 0, i = n - w + 1; i <= n; i++) tmp[++p] = i;
for (i = 1; i <= n; i++) if (SA[i] > w) tmp[++p] = SA[i] - w;
sort(n, m); std::swap(Rank, tmp); Rank[SA[1]] = p = 1;
for (i = 2; i <= n; i++) Rank[SA[i]] = cmp(tmp, SA[i], SA[i - 1], w, n) ? p : ++p;
}
int j, k = 0;
for (int i = 1; i <= n; Height[Rank[i]] = k, i++)
for (k = (k ? k - 1 : k), j = SA[Rank[i] - 1]; str[i + k] == str[j + k]; k++);
}
}

后缀自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
namespace SuffixAutomation {
struct node {
int minlen, maxlen, trans[26], slink;
}T[maxn]; int nodeCnt;
int newnode(int maxlen, int minlen, int* trans, int slink) {
T[nodeCnt].maxlen = maxlen;
T[nodeCnt].minlen = minlen;
T[nodeCnt].slink = slink;
if (trans != NULL)
for (int i = 0; i < 26; i++) T[nodeCnt].trans[i] = trans[i];
else
for (int i = 0; i < 26; i++) T[nodeCnt].trans[i] = -1;
return nodeCnt++;
}
int addchar(char ch, int u) {
int c = ch - 'a', v = u;
int z = newnode(T[u].maxlen + 1, -1, NULL, -1);
while (v != -1 && T[v].trans[c] == -1)
T[v].trans[c] = z, v = T[v].slink;
if (v == -1) {
T[z].minlen = 1; T[z].slink = 0; return z;
}
int x = T[v].trans[c];
if (T[v].maxlen + 1 == T[x].maxlen) {
T[z].slink = x; T[z].minlen = T[x].maxlen + 1; return z;
}
int y = newnode(T[v].maxlen + 1, -1, T[x].trans, T[x].slink);
T[z].minlen = T[x].minlen = T[y].maxlen + 1;
T[z].slink = T[x].slink = y;
int w = v;
while (w != -1 && T[w].trans[c] == x)
T[w].trans[c] = y, w = T[w].slink;
T[y].minlen = T[T[y].slink].maxlen + 1;
return z;
}
void build(char *s) {
newnode(0, 0, 0, -1);
for (int i = 0, j = 0; s[i]; i++)
j = addchar(s[i], j);
}
}

图论

最短路

  • $floyd$ 多源最短路 & 最短路径计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int maxn = 300 + 10;
int dis[maxn][maxn], way[maxn][maxn];
void init() {
memset(dis, 63, sizeof(dis));
}
void add(int x, int y, int z) {
dis[x][y] = dis[y][x] = std::min(dis[x][y], z);
way[x][y] = way[y][x] = 1;
}
void floyd(int n) {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis[i][j] == dis[i][k] + dis[k][j])
way[i][j] += way[i][k] * way[k][j];
else if (dis[i][j] > dis[i][k] + dis[k][j]){
dis[i][j] = dis[i][k] + dis[k][j];
way[i][j] = way[i][k] * way[k][j];
}
}
  • $spfa$ 单源最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void spfa(int s){
queue<int>q;
for(int i = 1; i <= size; i++) dis[i] = INT_MAX;
dis[s] = 0; q.push(s);
while(q.size()){
int u = q.front(); q.pop(); inq[u] = false;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(dis[v] - dis[u] > e[i].dis){
dis[v] = dis[u] + e[i].dis;
if(!inq[v]) inq[v] = true, q.push(v);
}
}
}
}
  • $dijkstra$ 单源最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dijkstra(int s){
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
q.push(make_pair(0, s));
for(int i = 1; i <= size; i++) dis[i] = INF_MAX;
dis[s] = 0;
while(q.size()){
int u = q.top().second; q.pop();
if(vis[u]) continue; vis[u] = true;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to; if(vis[v]) continue;
if(dis[v] - dis[u] > e[i].dis){
dis[v] = dis[u] + e[i].dis;
q.push(make_pair(dis[v], v));
}
}
}
}

最小生成树

  • $kruskal$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct edge { int a, b, w; };
bool cmpedge(edge x, edge y) { return x.w < y.w; }
std::vector<edge>e;
int kruskal(int n) {
mergefindSet s; s.clear(n);
int ans = 0, block = n;
std::sort(e.begin(), e.end(), cmpedge);
for (int i = 0; i < e.size(); i++) {
int a = e[i].a, b = e[i].b;
if (s.find(a) == s.find(b)) continue;
ans += e[i].w; s.merge(a, b);
block = ~-block; if (block == 1) return ans;
}
return -1;
}
  • $prim$

网络流

  • $dinic$ 网络流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
namespace MaxFlow {
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
const int inf = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1; q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
}
  • $zkw$ 最小费用最大流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
namespace MinCostMaxFlow {
const int maxm = 2e5;
const int maxn = 2e4;
const int inf = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
//memset(dis, -1, sizeof(int) * (t + 1));
memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (!~dis[v] || dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != -1;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, inf);
flow += tmp; cost += tmp * dis[s];
}
return std::make_pair(flow, cost);
}
}

动态图联通性(离线版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e3 + 10;
const int maxm = 500000 + 10;
const int oo = 1e9 + 7;
struct Node {
Node *son[2], *father;
int val, minval, ID; bool rev;
bool isroot() {
if (!father) return true;
return father->son[0] != this && father->son[1] != this;
}
bool who() {
return father->son[1] == this;
}
void maintain() {
minval = val;
if (son[0]) minval = min(minval, son[0]->minval);
if (son[1]) minval = min(minval, son[1]->minval);
}
void reverse() {
swap(son[0], son[1]); rev ^= 1;
}
void pushdown_once() {
if (!rev) return; rev = false;
if (son[0]) son[0]->reverse();
if (son[1]) son[1]->reverse();
}
void pushdown() {
if (!isroot()) father->pushdown(); pushdown_once();
}
void rotate() {
Node *f = father, *g = f->father;
bool a = who(), b = !a;
f->son[a] = son[b];
if (son[b])
son[b]->father = f;
son[b] = f;
father = g;
if (!f->isroot())
g->son[f->who()] = this;
f->father = this;
f->maintain(); maintain();
}
void splay() {
for (pushdown(); !isroot(); rotate())
if (!father->isroot())
if (who() ^ father->who()) rotate();
else father->rotate();
}
Node *access() {
for (Node *x = this, *y = 0; ; y = x, x = x->father) {
if (!x) return y;
x->splay();
x->son[1] = y;
x->maintain();
}
}
Node *root() {
access(); splay(); Node *cur = this;
while (cur->son[0])
cur = cur->son[0];
cur->splay(); return cur;
}
void makeroot() {
access(); splay(); reverse();
}
}pool[maxn << 2];
stack<Node*>recy;
Node *node[maxn];

Node *newNode(int val, int ID = 0) {
static int NodeCnt = 0; Node *cur = 0;
if (recy.size()) cur = recy.top(), recy.pop();
else cur = &pool[NodeCnt++];
cur->val = val;
cur->ID = ID;
cur->son[0] = cur->son[1] = cur->father = 0;
cur->rev = false;
cur->maintain();
return cur;
}

void delet(Node *cur) { recy.push(cur); }

void link(Node *a, Node *b) {
if (a->root() == b->root()) return;
a->makeroot(); a->father = b;
}
void cut(Node *a, Node *b) {
if (a->root() != b->root()) return;
a->makeroot(); b->access(); b->splay();
if (a->son[1]) return;
a->father = b->son[0] = 0;
b->maintain();
}

struct Edge {
Node *e, *u, *v; Edge() {}
Edge(Node *a, Node *b, Node *c) {
e = a; u = b; v = c;
}
}e[maxm];

bool flag[maxm];

int findedge(Node *u, Node *v) {
u->makeroot(); v->access(); v->splay();
Node *cur = v;
while (cur) {
if (cur->val == cur->minval) return cur->ID;
if (cur->son[0] && cur->son[0]->minval == cur->minval) cur = cur->son[0];
if (cur->son[1] && cur->son[1]->minval == cur->minval) cur = cur->son[1];
}
return 0;
}

void cutedge(int ID) {
if (flag[ID]) return;
flag[ID] = true;
cut(e[ID].e, e[ID].u);
cut(e[ID].e, e[ID].v);
delet(e[ID].e);
}

void linkedge(int u, int v, int val, int id) {
if (node[u]->root() == node[v]->root()) {
int ID = findedge(node[u], node[v]);
if (e[ID].e->val >= val) return void(flag[id] = true);
cutedge(ID);
}
e[id] = Edge(newNode(val, id), node[u], node[v]);
link(e[id].e, e[id].u);
link(e[id].e, e[id].v);
}

struct {
int Tim, Type, u, v;
} opt[maxm];
int mmp[maxn][maxn];

inline int read(int u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '0';
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}

int main() {
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
int n = read(), m = read();
for (int i = 1; i <= n; i++) node[i] = newNode(oo);
for (int i = 1; i <= m; i++) {
int t = opt[i].Type = read(), u = opt[i].u = read(), v = opt[i].v = read();
if (t == 0) {
mmp[u][v] = mmp[v][u] = i;
} else if (t == 1) {
int ID = mmp[u][v]; mmp[u][v] = mmp[v][u] = 0;
opt[ID].Tim = i; opt[i].Tim = ID;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (mmp[i][j] != 0)
opt[mmp[i][j]].Tim = oo - 1;
for (int i = 1; i <= m; i++) {
int t = opt[i].Type, u = opt[i].u, v = opt[i].v;
if (t == 0) linkedge(u, v, opt[i].Tim, i);
if (t == 1) cutedge(opt[i].Tim);
if (t == 2) puts(node[u]->root() == node[v]->root() ? "Y" : "N");
}
return 0;
}
/*
4 6
0 1 3
0 2 4
0 1 2
0 1 4
0 2 3
2 3 4


*/

计算几何

基本运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
namespace geo {
const double ee = 1e-9;
const double oo = 1e15;
bool equ(double x, double y) { return fabs(x - y) < ee; }
struct vec {
double x, y; vec() {}
vec(double x, double y) : x(x), y(y) {}
friend vec operator + (vec a, vec b) { return vec(a.x + b.x, a.y + b.y); }
friend vec operator - (vec a, vec b) { return vec(a.x - b.x, a.y - b.y); }
friend vec operator * (vec a, double b) { return vec(a.x * b, a.y * b); }
friend vec operator * (double b, vec a) { return a * b; }
friend vec operator / (vec a, double b) { return a * (1 / b); }
friend double operator * (vec a, vec b) { return a.x * b.x + a.y * b.y; }
friend double operator ^ (vec a, vec b) { return a.x * b.y - a.y * b.x; }
friend bool operator < (vec a, vec b) { return a.x < b.x || (equ(a.x, b.x) && a.y < b.y); }
friend bool operator == (vec a, vec b) { return equ(a.x, b.x) && equ(a.y, b.y); }
double dis() { return *this * *this; }
vec normal() { return vec(-y, x) / dis(); }
void read() { scanf("%lf%lf", &x, &y); x += (rand() % 1000 - 500) * ee; y += (rand() % 1000 - 500) * ee; }
void clear() { *this = *this / dis(); }
};
typedef vec poi;
struct seg {
vec a, b; seg() {}
seg(vec a, vec b) : a(a), b(b) {}
};
typedef seg rec;
typedef seg lin;
bool InRec(poi p, rec r) {
if (p.x > std::max(r.a.x, r.b.x)) return false;
if (p.x < std::min(r.a.x, r.b.x)) return false;
if (p.y > std::max(r.a.y, r.b.y)) return false;
if (p.y < std::min(r.a.y, r.b.y)) return false;
return true;
}
bool SegCosSeg(seg k, seg l) {
vec u = k.a - k.b;
if ((u ^ (l.a - k.b)) * (u ^ (l.b - k.b)) > 0) return false;
vec v = l.a - l.b;
if ((v ^ (k.a - l.b)) * (v ^ (k.b - l.b)) > 0) return false;
return true;
}
poi CosPoi(lin k, lin l) {
double S = fabs((k.a - l.a) ^ (k.b - l.a));
vec u = l.b - l.a; u.clear();
double L = S / fabs(u ^ (k.a - k.b));
return u * L + l.a;
}
struct tra {
poi a, b, c; tra() {}
void read() {
a.read(); b.read(); c.read();
}
};
}

数学基础

欧几里德算法及其扩展

1
2
3
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
1
2
3
4
5
6
7
// 返回 gcd(a, b) 与方程 ax + by = gcd(a, b) 的一组解 
// 如果 gcd(a, b) = 1,则 x 表示 a 在模 b 意义下的逆元
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) { x = 1; y = 0; return a; }
ll d = exgcd(b, a % b, y, x);
y -= a / b * x; return d;
}

中国剩余定理及其扩展

1
2
3
4
5
6
7
8
9
10
int china(int *a, int *m, int n) {
int M = 1, ans = 0, tmp;
for (int i = 1; i <= n; i++) M *= m[i];
for (int i = 1; i <= n; i++) {
int Mi = M / m[i], iMi;
exgcd(Mi, m[i], iMi, tmp);
ans = (ans + a[i] * Mi * iMi) % M;
}
return (M + ans % M) % M;
}
1
2
3
4
5
6
7
8
9
10
11
12
ll exchina(ll *a, ll *m, int n) {
ll A = a[1], M = m[1], t, d, x, y;
for (int i = 2; i <= n; i++) {
ll d = exgcd(M, m[i], x, y);
if ((a[i] - A) % d != 0) return -1;
x *= (a[i] - A) / d;
t = m[i] / d;
x = (t + x % t) % t;
A = M * x + A, M *= t, A %= M;
}
return (A % M + M) % M;
}

付费通(fft)快速离散卷积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct cpx {
double r, i; cpx() {}
cpx(double r, double i) :
r(r), i(i) {}
friend cpx operator * (cpx a, cpx b)
{ return cpx(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r); }
friend cpx operator + (cpx a, cpx b)
{ return cpx(a.r + b.r, a.i + b.i); }
friend cpx operator - (cpx a, cpx b)
{ return cpx(a.r - b.r, a.i - b.i); }
friend cpx operator / (cpx a, double b)
{ return cpx(a.r / b, a.i / b); }

};
namespace FFT {
int rev[maxn];
const double pi = acos(-1);
void fft(cpx *a, int n, int dft) {
for (int i = 0; i < n; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1) {
cpx rotate(cos(pi / i), dft * sin(pi / i));
for (int j = 0; j < n; j += (i << 1)) {
cpx x(1, 0);
for (int k = j; k < j + i; k++) {
cpx a1 = a[k], a2 = a[k + i];
a[k] = a1 + a2 * x; a[k + i] = a1 - a2 * x;
x = x * rotate;
}
}
}
}
void convolution(cpx *f, cpx *g, int n, int m) {
int s = 2, b = 1;
while (s < m + n - 1) s <<= 1, b++;
for (int i = 0; i < s; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (b - 1));
fft(f, s, 1);
fft(g, s, 1);
for (int i = 0; i < s; i++) f[i] = f[i] * g[i];
fft(f, s, -1);
for (int i = 0; i < s; i++) f[i] = f[i] / s;
}
}

$NTT$快速数论卷积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
namespace NTT {
const int P = (479 << 21) + 1, G = 3;
inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { ll r = ll(x) * y; return r >= P ? int(r % P) : int(r); }
inline int pow(int x, int y, int ans = 1) {
while (y) {
if (y & 1) ans = mul(ans, x);
y >>= 1, x = mul(x, x);
}return ans;
}
int rev[maxn];
void ntt(int *a, int n, int f) {
for (int i = 0; i < n; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1) {
int e = pow(f, (P - 1) / (i << 1));
for (int j = 0; j < n; j += (i << 1)) {
int x = 1;
for (int k = j; k < j + i; k++) {
int a1 = a[k], a2 = mul(x, a[k + i]);
a[k] = pls(a1, a2); a[k + i] = dec(a1, a2);
x = mul(x, e);
}
}
}
}
void convolution(int *f, int *g, int n, int m) {
int s = 2, b = 1; while (s < n + m - 1) s <<= 1, b++;
for (int i = 0; i < s; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (b - 1));
ntt(f, s, G); ntt(g, s, G);
for (int i = 0; i < s; i++) f[i] = mul(f[i], g[i]);
ntt(f, s, pow(G, P - 2)); int inv = pow(s, P - 2);
for (int i = 0; i < s; i++) f[i] = mul(f[i], inv);
}
}

附表:用到的各种素数及其原根

$r*2^k+1$ r k g
3 1 1 2
5 1 2 2
17 1 4 3
97 3 5 5
193 3 6 5
257 1 8 3
7681 15 9 17
12289 3 12 11
40961 5 13 3
65537 1 16 3
786433 3 18 10
5767169 11 19 3
7340033 7 20 3
23068673 11 21 3
104857601 25 22 3
167772161 5 25 3
469762049 7 26 3
998244353 119 23 3
1004535809 479 21 3
2013265921 15 27 31
2281701377 17 27 3
3221225473 3 30 5
75161927681 35 31 3
77309411329 9 33 7
206158430209 3 36 22
2061584302081 15 37 7
2748779069441 5 39 3
6597069766657 3 41 5
39582418599937 9 42 5
79164837199873 9 43 5
263882790666241 15 44 7
1231453023109121 35 45 3
1337006139375617 19 46 3
3799912185593857 27 47 5
4222124650659841 15 48 19
7881299347898369 7 50 6
31525197391593473 7 52 3
180143985094819841 5 55 6
1945555039024054273 27 56 5
4179340454199820289 29 57 3

多项式的各种操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
namespace poly {
const int P = 998244353;
const int E = 3;
const int maxn = 1e6 + 10;
inline int inc(int a, int b) { a += b; return a >= P ? a - P : a; }
inline int dec(int a, int b) { a -= b; return a < 0 ? a + P : a; }
typedef long long ll;
inline int mul(int a, int b) { return int(ll(a) * b % P); }
inline int ksm(int a, int b, int c = 1) {
for (; b; a = mul(a, a), b >>= 1)
if (b & 1) c = mul(a, c);
return c;
}
void dft(int *f, int n, int R) {
static int rev[maxn], Last = 0;
if (n != Last)
for (int i = 1; i < n; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1 ? (n >> 1) : 0);
Last = n;
for (int i = 0; i < n; ++i) if (i < rev[i]) swap(f[i], f[rev[i]]);
for (int i = 1; i < n; i <<= 1)
for (int e = ksm(R, (P - 1) / (i << 1)), j = 0; j < n; j += i << 1)
for (int x = 1, k = j; k < j + i; ++k, x = mul(x, e)) {
int a1 = f[k], a2 = f[k + i] * ll(x) % P;
f[k] = inc(a1, a2); f[k + i] = dec(a1, a2);
}
if (R != E) for (int I = ksm(n, P - 2), i = 0; i < n; ++i) f[i] = mul(f[i], I);
}
void conv(int *f, int *g, int *h, int n, int m) {
static int F[maxn], G[maxn];
int s = n + m - 1; while (s != (s & -s)) s += s & -s;
memset(F, 0, sizeof(int) * s); memset(G, 0, sizeof(int) * s);
for (int i = 0; i < n; ++i) F[i] = f[i];
for (int i = 0; i < m; ++i) G[i] = g[i];
dft(F, s, E); dft(G, s, E);
for (int i = 0; i < s; ++i) h[i] = mul(F[i], G[i]);
dft(h, s, ksm(E, P - 2));
}

void getdao(int *f, int *g, int n) {
for (int i = 0; i < n - 1; ++i) g[i] = mul(i + 1, f[i + 1]); g[n - 1] = 0;
}

void getfen(int *f, int *g, int n) {
static int inv[maxn], now = 1; inv[1] = 1;
while (now < n) ++now, inv[now] = dec(0, mul(inv[P % now], P / now));
for (int i = n - 1; i; i--) g[i] = mul(f[i - 1], inv[i]); g[0] = 0;
}

void getinv(int *f, int *g, int n) {
static int h[maxn];
if (n == 1) return void(g[0] = ksm(f[0], P - 2));
else {
int m = n + 1 >> 1;
getinv(f, g, m);
conv(f, g, h, n, m);
for (int i = 0; i < n; i++) h[i] = dec(0, h[i]); h[0] = inc(h[0], 2);
conv(g, h, g, m, n);
}

}

void getln(int *f, int *g, int n) {
static int h[maxn];
getdao(f, g, n);
getinv(f, h, n);
conv(g, h, g, n, n);
getfen(g, g, n);
}

void getexp(int *f, int *g, int n) {
static int h[maxn];
while (n != (n & -n)) n += n & -n;
if (n == 1) return void(g[0] = 1);
else {
int m = n >> 1;
getexp(f, g, m);
for (int i = m; i < n; i++) g[i] = 0;
getln(g, h, n);
for (int i = 0; i < n; i++)
h[i] = dec(f[i], h[i]);
h[0] = inc(h[0], 1);
conv(g, h, g, m, n);
}
}
}