Clairewd message

Description

Clairewd is a member of FBI. After several years concealing in BUPT, she intercepted some important messages and she was preparing for sending it to ykwd. They had agreed that each letter of these messages would be transfered to another one according to a conversion table.
Unfortunately, GFW(someone’s name, not what you just think about) has detected their action. He also got their conversion table by some unknown methods before. Clairewd was so clever and vigilant that when she realized that somebody was monitoring their action, she just stopped transmitting messages.
But GFW knows that Clairewd would always firstly send the ciphertext and then plaintext(Note that they won’t overlap each other). But he doesn’t know how to separate the text because he has no idea about the whole message. However, he thinks that recovering the shortest possible text is not a hard task for you.
Now GFW will give you the intercepted text and the conversion table. You should help him work out this problem.

Read More

矩阵游戏

Description

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。
她生成的这个矩阵满足一个神奇的性质:若用F[i][j]来表示矩阵中第i行第j列的元素,则F[i][j]满足下面的递推式:
F[1][1]=1
F[i,j]=a×F[i][j-1]+b(j!=1)
F[i,1]=c×F[i-1][m]+d(i!=1)
递推式中a,b,c,d都是给定的常数。
现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大,你只需要输出F[n][m]除以1,000,000,007的余数。

Read More

Matrix

Description

Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).

We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using “not” operation (if it is a ‘0’ then change it into ‘1’ otherwise change it into ‘0’). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.

  1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
  2. Q x y (1 <= x, y <= n) querys A[x, y].

    Read More

noip模拟赛2017.7.11

题目名称 中位数 敲砖块 单词 邮递员送信
提交文件 median.* brike.* words.* post.*
输入文件 median.in brike.in words.in post.in
输出文件 median.out brike.out words.out post.out
时间限制 1s 1s 1s 1s
空间限制 128MB 128MB 128MB 128MB

Read More

noip模拟赛2017.7.15

试题名称 猴子
提交文件 tower circle monkey hill
输入文件 tower.in circle.in monkey.in hill.in
输出文件 tower.out circle.out monkey.out hill.out
时间限制 1s 1s 1s 1s
空间限制 128MB 128MB 128MB 128MB

Read More

noip模拟赛2017.7.16

题目名称 黑魔法师之门 守卫者的挑战 终极武器
程序文件名 magician guard laser
输入文件名 magician.in guard.in laser.in
输出文件名 magician.out guard.out laser.out
每个测试点时限 1 秒 1 秒 2 秒
内存限制 128 MB 128 MB 128 MB
测试点数目 10 10 20
每个测试点分值 10 10 5
是否有部分分

Read More

noip模拟赛2017.7.7

题目名称 小猫爬山 Freda 的传呼机 Rainbow 的信号
程序文件名 catclimb communicate signal
输入文件名 catclimb.in communicate.in signal.in
输出文件名 catclimb.out communicate.out signal.out
每个测试点时限 1 秒 0.1 秒 1 秒
内存限制 128 MB 128 MB 128 MB
测试点数目 12 20 10
每个测试点分值 8.3333333333 5 10 (4+3+3)
是否有部分分
评测方式 Normal Normal Special Judge

Read More

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
namespace geometry {
const double ee = 1e-9;
const double oo = 1e15;
char tmp;
bool equ(double x, double y) {
return fabs(x - y) <= ee;
}
struct vec {
double x, y;
vec() { x = y = 0; }
vec(double x, double y) : x(x), y(y) {}
void read() {
std::cin >> tmp >> x >> tmp >> y >> tmp;
}
};
struct seg {
vec a, b;
seg() {}
seg(vec a, vec b) : a(a), b(b) {}
};
vec operator + (vec a, vec b) {
return vec(a.x + b.x, a.y + b.y);
}
vec operator - (vec a, vec b) {
return vec(a.x - b.x, a.y - b.y);
}
vec operator * (vec a, double b) {
return vec(a.x * b, a.y * b);
}
vec operator * (double b, vec a) {
return vec(a.x * b, a.y * b);
}
vec operator / (vec a, double b) {
return vec(a.x / b, a.y / b);
}
bool operator == (vec a, vec b) {
return equ(a.x, b.x) && equ(a.y, b.y);
}
double operator * (vec a, vec b) {
return a.x * b.x + a.y * b.y;
}
double operator ^ (vec a, vec b) {
return a.x * b.y - a.y * b.x;
}
double dis(vec a, vec b) {
return sqrt((a - b) * (a - b));
}
bool ptInRect(vec p, seg l) {
vec a = l.a, b = l.b;
if (p.x > std::max(a.x, b.x)) return false;
if (p.x < std::min(a.x, b.x)) return false;
if (p.y > std::max(a.y, b.y)) return false;
if (p.y < std::min(a.y, b.y)) return false;
return true;
}
bool ptOnSeg(vec p, seg l) {
return equ((l.a - l.b) ^ p, 0) && ptInRect(p, l);
}
bool segCntLine(seg s, seg l) {
return ((s.a - l.a) ^ (l.b - l.a)) * ((s.b - l.a) ^ (l.b - l.a)) >= 0;
}
bool segCrossSeg(seg l1, seg l2) {
if (!ptInRect(l1.a, l2)) return false;
if (!ptInRect(l1.b, l2)) return false;
if (!segCntLine(l1, l2)) return false;
if (!segCntLine(l2, l1)) return false;
return true;
}
}

数学基础

付费通(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

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2018 Anoxiacxy All Rights Reserved.

UV : | PV :