「学习笔记」是男人就用树剖

「学习笔记」是男人就用树剖

概括

树链剖分是个什么玩意儿呢~
其实我是理解了好一会儿的。
首先,树链剖分是为了快速维护树上问题应运而生的。其特点是能够将树上的链转化成可以进行维护范围内的短链的组合。
最常用的剖分是轻重链剖分法。

定义

对于每一个节点$k$,定义其子节点中子树最大的点为其重儿子,$son[k]$,而连接某节点和其重儿子的边$(u, v)$叫做重边。显然,重边一定是可连续的,因为每个点都有其重儿子。连续的重边叫做重链。剩余的边叫做轻链。这样,我们就将一棵树划分为轻链和重链。

复杂度证明

对于任意一个轻边连接的两个节点,$u, v$。一定存在$siz[u] > 2 * siz[v]$。不然其之间一定是重边。也就是说,对于距离根节点最远的节点$k$,到根节点总共经过的轻边的个数一定$\leq logn$。轻边和重边是对应的。所以重边也是$logn$的。
树链剖分最终的复杂度是你使用的数据结构乘上$logn$。

这个logn哪来的?

一开始可能会不好理解,我们从Lca入手来看。顺带把实现也给看了。

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
struct Node
{
int siz, son, fa, dep, id, top;
} t[maxn];
int n, m, s, cnt;
int head[maxn], next[maxn << 1], ver[maxn << 1], tot;

inline void addedge(R int from, R int to)
{
ver[++tot] = to, next[tot] = head[from], head[from] = tot;
}

inline void dfs1(R int k)
{
t[k].siz = 1, t[k].son = 0; // fuck
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if(to == t[k].fa) continue;
// 这样初始化的成本貌似低一些,先这么写吧。
t[to].fa = k, t[to].dep = t[k].dep + 1;
dfs1(to);
if(t[to].siz > t[t[k].son].siz) t[k].son = to;
t[k].siz += t[to].siz;
}
}

inline void dfs2(R int k, R int topf)
{
t[k].id = ++cnt, t[k].top = topf;
if(!t[k].son) return;
dfs2(t[k].son, topf);
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if(to == t[k].fa || to == t[k].son) continue;
dfs2(to, to); // 对于每一个轻儿子,都是从自己开始的
}
}

inline int lca(R int x, R int y)
{
while(t[x].top != t[y].top)
{
if(t[t[x].top].dep >= t[t[y].top].dep) x = t[t[x].top].fa;
else y = t[t[y].top].fa;
}
return t[x].dep > t[y].dep ? y : x;
}

其中的俩函数$dfs1$, $dfs2$分别完成了$fa, siz, dep, son$和$top, id$的加载,有些需要维护的时候,$dfs2$也需要加载需要维护的信息。这个之后的代码会有所体现。
对应到跳跳跳的方式上,我们可以看到,每次选取$top$最深的节点,把这个节点提到这个链的顶端,然后总结经过的这条链的信息(这里没有)。最后,这俩会跳到一条链上去,然后总结这俩之间的关系就好啦~

标题,是男人就用树剖,女人才用倍增()

dfs序和链剖的结合

如果有一道题,既需要维护子树的信息,有需要维护链的信息,我们该咋做?

这里,LUOGU3384。需要同时维护链和子树的信息。
在dfs序中,子树一定处于连续区间,而链也处于连续区间。通过这个性质,我们可以把链和子树放到一起去。同时带上一个较简单的线段树维护。
代码可以说是很长了…真的很长了…我写了带数据结构维护的都没有下5kb。

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// #define DEBUG
#define ll long long
#define R register
#define ls t[k].son[0]
#define rs t[k].son[1]
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

namespace IO
{
inline char gc()
{
static char buf[1 << 18], *fs, *ft;
return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read()
{
register int k = 0, f = 1;
register char c = gc();
for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
return k * f;
}
}

namespace Template
{
struct Node
{
int l, r, son[2];
ll sum, add;
Node() {}
} t[maxn << 1];
int head[maxn], ver[maxn << 1], next[maxn << 1], tot;
int siz[maxn], top[maxn], fa[maxn], son[maxn], dep[maxn], id[maxn], wt[maxn], w[maxn], cnt, tcnt;
int n, m, r, p, root;

template<typename T>
inline void inc(T &a, T b)
{
a = (1ll * a + b) % p;
}

inline void addedge(R int from, R int to)
{
ver[++tot] = to, next[tot] = head[from], head[from] = tot;
}

inline void dfs1(R int k)
{
siz[k] = 1, son[k] = 0;
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if(to == fa[k]) continue;
fa[to] = k, dep[to] = dep[k] + 1;
dfs1(to);
if(siz[to] > siz[son[k]]) son[k] = to;
siz[k] += siz[to];
}
}

inline void dfs2(R int k, R int topf)
{
id[k] = ++tcnt, wt[tcnt] = w[k], top[k] = topf;
if(!son[k]) return;
dfs2(son[k], topf);
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if(to == fa[k] || to == son[k]) continue;
dfs2(to, to);
}
}

inline void pushup(R int k)
{
t[k].sum = (t[ls].sum + t[rs].sum) % p;;
}

inline void pushdown(R int k)
{
if(t[k].add)
{
inc(t[ls].add, t[k].add), inc(t[rs].add, t[k].add);
inc(t[ls].sum, t[k].add * (t[ls].r - t[ls].l + 1));
inc(t[rs].sum, t[k].add * (t[rs].r - t[rs].l + 1));
t[k].add = 0;
}
}

inline void build(int &k, R int l, R int r)
{
k = ++cnt, t[k].l = l, t[k].r = r;
if(l == r) return t[k].sum = wt[l], void();
R int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(k);
}

inline void addrange(R int k, R int l, R int r, R int val)
{
if(t[k].l == l && t[k].r == r)
return inc(t[k].add, (ll)val), inc(t[k].sum, 1ll * val * (r - l + 1)), void();
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if (r <= mid) addrange(ls, l, r, val);
else if (l > mid) addrange(rs, l, r, val);
else addrange(ls, l, mid, val), addrange(rs, mid + 1, r, val);
pushup(k);
}

inline ll queryrange(R int k, R int l, R int r)
{
if(t[k].l == l && t[k].r == r)
return t[k].sum;
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if(r <= mid) return queryrange(ls, l, r) % p;
else if (l > mid) return queryrange(rs, l, r) % p;
else return (queryrange(ls, l, mid) % p + queryrange(rs, mid + 1, r) % p) % p;
}

inline ll querytree(int x, int y)
{
R ll ans = 0, tmp = 0;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
tmp = queryrange(root, id[top[x]], id[x]);
inc(ans, tmp);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
inc(ans, queryrange(root, id[x], id[y]));
return ans;
}

inline void modifytree(int x, int y, int val)
{
val %= p;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
addrange(root, id[top[x]], id[x], val);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
addrange(root, id[x], id[y], val);
}

inline ll querysubtree(int x)
{
return queryrange(root, id[x], id[x] + siz[x] - 1);
}

inline void modifysubtree(int x, int val)
{
addrange(root, id[x], id[x] + siz[x] - 1, val % p);
}

inline void solve()
{
// freopen("QAQ.txt", "r", stdin);
using namespace IO;
n = read(), m = read(), r = read(), p = read();
for (R int i = 1; i <= n; ++i) w[i] = read();
R int x, y, z, op;
for (R int i = 1; i < n; ++i)
x = read(), y = read(), addedge(x, y), addedge(y, x);
dfs1(r), dfs2(r, r);
build(root, 1, n);
for (R int i = 1; i <= m; ++i)
{
op = read();
switch(op)
{
case 1: x = read(), y = read(), z = read(), modifytree(x, y, z); break;
case 2: x = read(), y = read(), printf("%lld\n", querytree(x, y)); break;
case 3: x = read(), z = read(), modifysubtree(x, z); break;
case 4: x = read(), printf("%lld\n", querysubtree(x)); break;
}
}
#ifdef DEBUG
for (R int i = 1; i <= n; ++i)
printf("id: %d -> son: %d\n", i, top[i]);
for (R int i = 1; i <= n; ++i)
printf("node_id: %d -> node.sum: %d\n", i, t[i].sum);
#endif
}
}

int main()
{
return Template::solve(), 0;
}

例题~

BZOJ2243 染色

简单提一下,链和链之间也是需要类似线段树的$pushup$的。这道题有所体现。
我放两个版本,讨论常数的问题。

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#define ll long long
#define R register
#define ls t[k].son[0]
#define rs t[k].son[1]
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

namespace IO
{
inline char gc()
{
static char buf[1 << 18], *fs, *ft;
return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read()
{
register int k = 0, f = 1;
register char c = gc();
for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
return k * f;
}
inline char read_c()
{
register char c;
for (c = gc(); isspace(c); c = gc());
return c;
}
}

namespace BZOJ2243
{
struct Node
{
int l, r, set, son[2];
ll cols, lc, rc;
Node() {}
} t[maxn << 1];
int siz[maxn], son[maxn], fa[maxn], dep[maxn], id[maxn],
tcol[maxn], col[maxn], top[maxn];
int head[maxn], next[maxn << 1], ver[maxn << 1], tot;
int n, m, root, cnt, tcnt;

inline void addedge(int from, int to)
{
ver[++tot] = to, next[tot] = head[from], head[from] = tot;
}

inline void dfs1(int k)
{
siz[k] = 1, son[k] = 0;
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if (to == fa[k]) continue;
fa[to] = k, dep[to] = dep[k] + 1;
dfs1(to);
if (siz[to] > siz[son[k]]) son[k] = to;
siz[k] += siz[to];
}
}

inline void dfs2(int k, int topf)
{
id[k] = ++cnt, tcol[cnt] = col[k], top[k] = topf;
if (!son[k]) return;
dfs2(son[k], topf);
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if (to == fa[k] || to == son[k]) continue;
dfs2(to, to);
}
}

inline void pushup(int k)
{
// 如果中间相同,那么就 - 1, 否则就是两边的块数相加~
t[k].cols = t[ls].cols + t[rs].cols - (t[ls].rc == t[rs].lc);
t[k].lc = t[ls].lc, t[k].rc = t[rs].rc;
}

inline void pushdown(int k)
{
if (t[k].set)
{
t[ls].set = t[rs].set = t[k].set;
t[ls].lc = t[ls].rc = t[rs].lc = t[rs].rc = t[k].set;
t[ls].cols = t[rs].cols = 1;
t[k].set = 0;
}
}

inline void build(int &k, int l, int r)
{
k = ++tcnt; t[k].l = l, t[k].r = r;
if (l == r) return t[k].lc = t[k].rc = tcol[l], t[k].cols = 1, void();
R int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(k);
}

// TODO: mrange, qpoint, qrange

inline void mrange(int k, int l, int r, int c)
{
if (t[k].l == l && t[k].r == r)
return t[k].lc = t[k].rc = c, t[k].cols = 1, t[k].set = c, void();
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if (r <= mid) mrange(ls, l, r, c);
else if (l > mid) mrange(rs, l, r, c);
else mrange(ls, l, mid, c), mrange(rs, mid + 1, r, c);
pushup(k);
}

inline int qpoint(int k, int pos)
{
if (t[k].l == t[k].r && t[k].l == pos)
return t[k].lc;
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if (pos <= mid) return qpoint(ls, pos);
else return qpoint(rs, pos);
}

inline int qrange(int k, int l, int r)
{
if (t[k].l == l && t[k].r == r)
return t[k].cols;
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if (r <= mid) return qrange(ls, l, r);
else if (l > mid) return qrange(rs, l, r);
else {
int tmp = qrange(ls, l, mid) + qrange(rs, mid + 1, r);
tmp -= (t[ls].rc == t[rs].lc);
return tmp;
}
}

inline int qtree(int x, int y)
{
R int ans = 0;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
ans += qrange(root, id[top[x]], id[x]);
ans -= (qpoint(root, id[top[x]]) == qpoint(root, id[fa[top[x]]]));
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ans += qrange(root, id[x], id[y]);
return ans;
}

inline void mtree(int x, int y, int c)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
mrange(root, id[top[x]], id[x], c);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
mrange(root, id[x], id[y], c);
}

inline void solve()
{
using namespace IO;
n = read(), m = read();
for (R int i = 1; i <= n; ++i) col[i] = read();
R int x, y, z;
for (R int i = 1; i < n; ++i)
x = read(), y = read(),
addedge(x, y), addedge(y, x);
dfs1(1), dfs2(1, 1);
build(root, 1, n);
R char op;
for (R int i = 1; i <= m; ++i)
{
op = read_c();
switch(op)
{
case 'C': x = read(), y = read(), z = read(), mtree(x, y, z); break;
case 'Q': x = read(), y = read(), printf("%d\n", qtree(x, y)); break;
}
}
}
}

int main()
{
return BZOJ2243::solve(), 0;
}

下面是struct版本的。

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#define ll long long
#define R register
#define ls t[k].son[0]
#define rs t[k].son[1]
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

namespace IO
{
inline char gc()
{
static char buf[1 << 18], *fs, *ft;
return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read()
{
register int k = 0, f = 1;
register char c = gc();
for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
return k * f;
}
inline char read_c()
{
register char c;
for (c = gc(); isspace(c); c = gc());
return c;
}
}

namespace BZOJ2243
{
struct Node
{
int l, r, set, son[2];
ll cols, lc, rc;
Node() {}
} t[maxn << 1];
struct TNode
{
int siz, son, fa, dep, id, col, top;
} q[maxn];
// int siz[maxn], son[maxn], fa[maxn], dep[maxn], id[maxn],
// tcol[maxn], col[maxn], top[maxn];
int head[maxn], next[maxn << 1], ver[maxn << 1], tot;
int n, m, root, cnt, tcnt, tcol[maxn];

inline void addedge(int from, int to)
{
ver[++tot] = to, next[tot] = head[from], head[from] = tot;
}

inline void dfs1(int k)
{
q[k].siz = 1, q[k].son = 0;
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if (to == q[k].fa) continue;
q[to].fa = k, q[to].dep = q[k].dep + 1;
dfs1(to);
if (q[to].siz > q[q[k].son].siz) q[k].son = to;
q[k].siz += q[to].siz;
}
}

inline void dfs2(int k, int topf)
{
q[k].id = ++cnt, tcol[cnt] = q[k].col, q[k].top = topf;
if (!q[k].son) return;
dfs2(q[k].son, topf);
for (R int i = head[k]; i; i = next[i])
{
R int to = ver[i];
if (to == q[k].fa || to == q[k].son) continue;
dfs2(to, to);
}
}

inline void pushup(int k)
{
// 如果中间相同,那么就 - 1, 否则就是两边的块数相加~
t[k].cols = t[ls].cols + t[rs].cols - (t[ls].rc == t[rs].lc);
t[k].lc = t[ls].lc, t[k].rc = t[rs].rc;
}

inline void pushdown(int k)
{
if (t[k].set)
{
t[ls].set = t[rs].set = t[k].set;
t[ls].lc = t[ls].rc = t[rs].lc = t[rs].rc = t[k].set;
t[ls].cols = t[rs].cols = 1;
t[k].set = 0;
}
}

inline void build(int &k, int l, int r)
{
k = ++tcnt; t[k].l = l, t[k].r = r;
if (l == r) return t[k].lc = t[k].rc = tcol[l], t[k].cols = 1, void();
R int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(k);
}

// TODO: mrange, qpoint, qrange

inline void mrange(int k, int l, int r, int c)
{
if (t[k].l == l && t[k].r == r)
return t[k].lc = t[k].rc = c, t[k].cols = 1, t[k].set = c, void();
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if (r <= mid) mrange(ls, l, r, c);
else if (l > mid) mrange(rs, l, r, c);
else mrange(ls, l, mid, c), mrange(rs, mid + 1, r, c);
pushup(k);
}

inline int qpoint(int k, int pos)
{
if (t[k].l == t[k].r && t[k].l == pos)
return t[k].lc;
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if (pos <= mid) return qpoint(ls, pos);
else return qpoint(rs, pos);
}

inline int qrange(int k, int l, int r)
{
if (t[k].l == l && t[k].r == r)
return t[k].cols;
pushdown(k);
R int mid = (t[k].l + t[k].r) >> 1;
if (r <= mid) return qrange(ls, l, r);
else if (l > mid) return qrange(rs, l, r);
else {
int tmp = qrange(ls, l, mid) + qrange(rs, mid + 1, r);
tmp -= (t[ls].rc == t[rs].lc);
return tmp;
}
}

inline int qtree(R int x, R int y)
{
R int ans = 0;
while (q[x].top != q[y].top)
{
if (q[q[x].top].dep < q[q[y].top].dep) swap(x, y);
ans += qrange(root, q[q[x].top].id, q[x].id);
ans -= (qpoint(root, q[q[x].top].id) == qpoint(root, q[q[q[x].top].fa].id));
x = q[q[x].top].fa;
}
if (q[x].dep > q[y].dep) swap(x, y);
ans += qrange(root, q[x].id, q[y].id);
return ans;
}

inline void mtree(R int x, R int y, R int c)
{
while (q[x].top != q[y].top)
{
if (q[q[x].top].dep < q[q[y].top].dep) swap(x, y);
mrange(root, q[q[x].top].id, q[x].id, c);
x = q[q[x].top].fa;
}
if (q[x].dep > q[y].dep) swap(x, y);
mrange(root, q[x].id, q[y].id, c);
}

inline void solve()
{
using namespace IO;
n = read(), m = read();
for (R int i = 1; i <= n; ++i) q[i].col = read();
R int x, y, z;
for (R int i = 1; i < n; ++i)
x = read(), y = read(),
addedge(x, y), addedge(y, x);
dfs1(1), dfs2(1, 1);
build(root, 1, n);
R char op;
for (R int i = 1; i <= m; ++i)
{
op = read_c();
switch(op)
{
case 'C': x = read(), y = read(), z = read(), mtree(x, y, z); break;
case 'Q': x = read(), y = read(), printf("%d\n", qtree(x, y)); break;
}
}
}
}

int main()
{
return BZOJ2243::solve(), 0;
}

常数问题

其实,要说链剖本身的常数,是比较小的…
都怪套在里面的…
优化技巧的话,BZOJ老年机加了struct快了100ms,luogu的加了慢了400ms。这就看CCF到底是不是老年机了(废话)
并且,由于递归,没法连续访问内存的问题,vector大数据下没有优势,慎用,裸Lca会慢将近一倍。

「BZOJ2190」仪仗队

我们这么考虑
对于一个点$(x, y)$
他的爸爸$(kx, ky)$一定不能被看到。
那么对于一个点$(x, y)$, $gcd(x, y) == 1$
$gcd(kx, ky) = k$,肯定不行啦~
换一种说法,对于一个点,$gcd(x, y) = b$
那么一定存在点$(x / b, y / b)$可以被看到
所以,被看到的一定是坐标互质的~
所以,就是要统计$x \in (1..n),y \in (1..n)$且$gcd(x, y) == 1$的个数
然后,forforfor肯定不行啦~这么吧,用$phi$啊!互质的个数嘛~
然后结果是$3 + \sum_{i = 2}^{n}{phi[i]}$

然后是递推$phi$

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
#define ll long long
#define R register
#include <bits/stdc++.h>

using namespace std;

const int maxn = 40005;

ll n, prm[maxn], cnt, phi[maxn], ans;
bitset<maxn> vis;

int main()
{
scanf("%lld", &n);
phi[1] = 1;
for (R int i = 2; i <= n; ++i)
{
if(!vis[i])
prm[++cnt] = i, phi[i] = i - 1;
for (R int j = 1; j <= cnt; ++j)
{
if(i * prm[j] > n) break;
vis[i * prm[j]] = 1;
if(i % prm[j] == 0)
{
phi[i * prm[j]] = phi[i] * prm[j];
break;
} else phi[i * prm[j]] = phi[i] * phi[prm[j]];
}
}
for (R int i = 2; i < n; ++i)
ans += (phi[i] << 1);
printf("%lld", ans == 0 ? ans : ans + 3);
}

「题解」「HNOI2011 」数学作业

oi

「HNOI2011 」数学作业

(默默放下了手中的数学作业,因为基本一下子就想到了这道题辣qwq

说明

解决时间:$1:47:58h$

我们首先看递推式
$f[n] = f[n - 1] \cdot 10^{len(n)} + n$
注意…写在代码里的时候需要$+1$..坑了我好一会儿
然后,我们发现,这玩意儿根本没法快速幂啊!!!
然后呢,于是呢,就想到了分段求解
我们把要求解的分成$[0, 9], [10, 99], [100, 999], [1000, 9999]…$
然后算矩阵递推式

$$
\begin{bmatrix}
10^{len(n)} & 1 & 1\
0 & 1 & 1\
0 & 0 & 1 \
\end{bmatrix}
\times
\begin{bmatrix}
fn \
n \
1
\end{bmatrix}=
\begin{bmatrix}
f
{n +1} \
n + 1 \
1
\end{bmatrix}
$$

错误

  1. 矩阵乘法写错 n…这回写成`ans[i][j] +=(a[i][k] val[k][j] % MOD)莫名没过...然后改成ll ans = 0;`才过的
  2. unsigned long long? 虽然只卡了一会儿
  3. 还有trans的时候,如果_r $<$ _l的时候回炸掉?

代码如下

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
#define ull unsigned long long
#define R register
#include <bits/stdc++.h>

using namespace std;

const int siz = 5;

namespace BZOJ2326
{
ull n, l, MOD;

struct Matrix
{
ull n, m, a[siz][siz];

Matrix()
{
memset(a, 0, sizeof(a));
for (R int i = 0; i < siz; ++i) a[i][i] = 1;
}
Matrix(int _n, int _m) : n(_n), m(_m)
{
memset(a, 0, sizeof(a));
for (R int i = 0; i < siz; ++i) a[i][i] = 1;
}

ull* operator [] (int x)
{
return a[x];
}

inline Matrix operator * (Matrix val)
{
Matrix ans(this->n, val.m);
R int i, j, k;
for (i = 1; i <= this->n; ++i)
for (j = 1; j <= val.m; ++j)
{
ull res = 0;
for (k = 1; k <= this->n; ++k)
res += (a[i][k] * val[k][j] % MOD);
ans[i][j] = res;
}
return ans;
}
inline Matrix pow(ull p)
{
if(n != m) return Matrix(this->n, this->n);
Matrix ans(this->n, this->n), t = *this;
for (; p; p >>= 1)
{
if(p & 1) ans = t * ans;
t = t * t;
}
return ans;
}
} qwq(3, 1), tmp(3, 3);

inline ull pow(ull a, ull p)
{
ull ans = 1; a %= MOD;
for (; p; p >>= 1)
{
if(p & 1) ans = (a * ans) % MOD;
a = (a * a) % MOD;
}
return ans;
}

inline int len(ull val)
{
int cnt = 0;
while(val) ++cnt, val /= 10;
return cnt;
}

inline void trans(Matrix &val, ull _l, ull _r)
{
_r = (_l % 10 ? _r : _r + 1);
tmp[1][1] = pow(10, len(_l));
val = tmp.pow(_r - _l) * val;
}

inline void solve()
{
scanf("%lld%lld", &n, &MOD);
qwq[1][1] = qwq[2][1] = qwq[3][1] = 1;
tmp[1][2] = tmp[1][3] = tmp[2][2] = tmp[2][3] = tmp[3][3] = 1;
R ull l = 1, r = 9;
for (; r <= n; l *= 10, r = l * 10 - 1) trans(qwq, l, r);
trans(qwq, l, n);
printf("%lld", qwq[1][1] % MOD);
}
}

int main()
{
return BZOJ2326::solve(), 0;
}

暑假集训

kririrae 2018 - 7 - 8学习笔记

互质

$gcd(a, b) = 1$

$gcd(a, b) = gcd(b, a \% b)$

$d = gcd(a, b)$
$a = d \cdot x_1, b = d \cdot x_2 \rightarrow gcd(x_1, x_2) = 1$

1
2
3
4
inline void gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}

$ax + by = gcd(a, b)$…

求$x, y$
$ax_1 + by_1 = gcd(a, b)$
$bx_2 + (a \% b)y_2 = gcd(b, a \% b)$
$\Rightarrow ax_1 + by_1 = bx_2 + (a \% b)y_2$
$a \% b = a - \lfloor\frac{a}{b}\rfloor \cdot b$
$\Rightarrow ax_1 + by_1 = bx_2 + (a - \lfloor\frac{a}{b}\rfloor \cdot b)y_2$

1
2
3
4
5
6
7
8
9
10
11
12
inline void exgcd(int &x, int &y, int a, int b)
{
if(b) exgcd(y, x, b, a % b), y -= (a / b) * x;
else x = 1, y = 0;
}

inline void exgcd(int &x, int &y, int a, int b)
{
int x2, y2;
if(b) exgcd(x2, y2, b, a % b), x = y2, y = x2 - (a / b) * y2;
else x = 1, y = 0;
}

逆元

$a \% p$意义下的逆元$b$, $(b \cdot a) \% p \equiv 1$。
$\frac{c}{b} \% p = (a \cdot c) \% p$转换为了乘法的取模qwq…

费马小定理

mod 为 质数的时候,$a^{mod} \% mod = a \Rightarrow a ^ {mod - 1} \% mod = 1 \Rightarrow (a \cdot a ^ {mod - 2}) \% mod = 1$
所以$a^{mod - 2}$是它的逆元,可以快速幂一下。

拓展欧几里得法

$ax + py = gcd(a, p) = 1 \Rightarrow ax \% p = 1$

中国单身定理

$y = a_1\;mod\;m_1$
$y = a_2\;mod\;m_2$
$y = a_3\;mod\;m_3$
$gcd(m_1, m_2, m_3) = 1$
解$y$
没听懂orz
先看高斯消元
如果没有$gcd = 1$
$y = a_1 + m_1x_1$
$y = a_2 + m_2x_2$
$\Rightarrow m_1x_1 - m_2x_2 = a_2 - a_1$
然后我们尝试用$exgcd$去解这一个方程
$\Rightarrow m_1x_1 - m_2x_2 = gcd(m_1, m_2)$
$\Rightarrow \frac{a_2 - a_1}{gcd(m_1, m_2)}(m_1x_1 - m_2x_2) = gcd(m_1, m_2) \cdot \frac{a_2 - a_1}{gcd(m_1, m_2)}$
然后解出来的$x_1, x_2$同时翻倍,解决~

高斯消元

$n < m$的时候
$a_1x_1 + a_2x_2 + a_3x_3 = 0$
$b_1x_1 + b_2x_2 + b_3x_3 = 0$
现在我们要解出x_1, x_2, x_3有无数组解
$n = m$的时候一组解
$a_1x_1 + a_2x_2 = 0$
$b_1x_1 + b_2x_2 = 0$
$n > m$的时候可能无解
$a_1x_1 + a_2x_2 = 0$
$b_1x_1 + b_2x_2 = 0$
$c_1x_1 + c_2x_2 = 0$

$$
\begin{bmatrix}
a{11} & a{12} & a{13} & a{14} \
a{21} & a{22} & a{23} & a{24} \
a{31} & a{32} & a{33} & a{34} \
a{41} & a{42} & a{43} & a{44} \
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
b{11} & b{12} & b{13} & b{14} \
0 & b{22} & b{23} & b{24} \
0 & 0 & b
{33} & b{34} \
0 & 0 & 0 & b
{44} \
\end{bmatrix}
\begin{bmatrix}
c{11} & 0 & 0 & 0 \
0 & c
{22} & 0 & 0 \
0 & 0 & c{33} & 0 \
0 & 0 & 0 & c
{44} \
\end{bmatrix}
$$
然后就解完了www…

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
struct Matrix
{
int n, m, rk;
// n -> 行数 m -> 列数
double ma[maxn][maxn];

void convert()
{
for (R int k = 1; k <= m; ++k)
{
double maxv = -1e9;
int maxp = k + 1;
for (R int i = k + 1; i <= n; ++i)
if(ma[i][k] > maxv) maxv = ma[i][k], maxp = i;
if(maxp != k + 1)
for (int j = 1; j <= m; ++j)
swap(ma[k + 1][j], ma[maxp][j]);
for (R int i = k + 1; i <= n; ++i)
{
double d = ma[k][k] / ma[i][k];
for (R int j = 1; j <= m; ++j)
ma[i][j] *= d, ma[i][j] -= ma[k][j];
}
}
for (R int i = 1; i <= n; ++i)
for (R int j = 1; j < m; ++j)
if(fabs(ma[i][j]) > eps) {
++rk;
break;
}
}

void trace()
{
for (R int k = m - 1; k >= 1; --k)
{
for (R int i = n - 1 - (m - 1 - k); i >= 1; --i)
{
double d = ma[k][k] / ma[i][k];
for (R int j = m; j >= 1; --j)
ma[i][j] *= d, ma[i][j] -= ma[k][j];
}
}
}

Matrix() { memset(ma, 0, sizeof(ma)); }
Matrix(int a, int b) : n(a), m(b) { }
};

这个板子是写死我了…

BZOJ1770
LUOGU3868
BZOJ3240

Atcoder爽题集合

Atcoder爽题集合

口胡和完整代码参见代码仓库

AtcoderGC019B

对于字符串$S$,每次可以选取$1 \leq i \leq j \leq n$的一个串使其倒过来,每次只能进行一次操作,求最终能够获得的字符串个数

1
2
3
4
5
6
scanf("%s", s + 1);
ll len = strlen(s + 1), ans = 1ll * len * (len + 1) / 2;
for (R int i = 1; i <= len; ++i) ++cnt[s[i] - 'a'];
for (R int i = 0; i <= 'z' - 'a'; ++i)
ans -= (1ll * cnt[i] * (cnt[i] - 1) / 2);
printf("%lld", ans - len + 1);

AtcoderGC024B

对于$[1 .. n]$的排列$A$, 每次可以选择一个数放到开头, 最后使得数列有序, 求最少操作次数. 简单dp

1
2
3
4
5
scanf("%d", &n);
for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = 1; i <= n; ++i)
f[a[i]] = f[a[i] - 1] + 1, ans = max(ans, f[a[i]]);
printf("%d", n - ans);

AtcoderGC022C

对于数列$A$, $B$, 每一次可以选择$A$中任意多个数, 然后选择一个数$k$, 使得每个选择的数$a_i$ 变成$a_i \; mod \; k$.然后代价是$2^k$, 最后使得$A$和$B$相同, 求代价最小值. 贪心 + 状压dp

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
scanf("%d", &n);
for (int j = 0; j <= 50; ++j)
{
f[j] = 0, f[j] |= (1ll << j);
for (int k = 1; k <= j; ++k)
if(((1ll << 51) - 1) & (1ll << k)) f[j] |= f[j % k];
}
for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = 1; i <= n; ++i) scanf("%d", &b[i]);
int flag = 1;
for (R int j = 1; j <= n; ++j)
if((f[a[j]] & (1ll << b[j])) == 0) flag = 0;
if(flag == 0) return printf("%lld\n", -1ll), void();
for (int i = 50; i; --i)
{
for (int j = 0; j <= 50; ++j)
{
f[j] = 0, f[j] |= (1ll << j);
for (int k = 1; k <= j; ++k)
if((ans + (1ll << i) - 1) & (1ll << k)) f[j] |= f[j % k];
}
int flag = 1;
for (R int j = 1; j <= n; ++j)
if((f[a[j]] & (1ll << b[j])) == 0) flag = 0;
if(!flag) ans += (1ll << i);
}
printf("%lld\n", ans);

AtcoderGC024C

对于初始为0的数列$A$, 每次可以选择一个$ai$变成$a{i - 1} + 1$.最后使得$A$变成$B$, 求最少操作次数. 蜜汁性质

1
2
3
4
5
6
7
8
9
10
11
scanf("%d", &n);
for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = 1; i <= n; ++i)
if(a[i] >= i) return puts("-1"), 0;
for (R int i = 2; i <= n; ++i)
{
if(a[i] - a[i - 1] > 1) return puts("-1"), 0;
if(a[i] == a[i - 1] + 1) ++ans;
else ans += a[i];
}
printf("%d\n", ans);

AtcoderGC020C

对于数列$A$的所有子集之和, 进行排序, 然后求出排序后的中位数
这道题值得提一提 补集思想很重要

1
2
3
4
5
scanf("%d", &n);
f[0] = 1;
for (R int i = 1; i <= n; ++i) scanf("%d", &val), f |= (f << val), sum += val;
if(n == 1) return printf("%d", sum), 0;
for (R int i = (sum >> 1); i; --i) if(f[i]) return printf("%d", sum - i), 0;