2019.2.19寒假集训-元宵爆零赛

发表于 | 分类于 | ℃热度
~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

恭喜您获得ysy大爷的毒瘤题一套

img

img

img

img

恭喜您获得爆零的好成绩

题解

tree：

首先不难发现，如果img某一步是朝着t走的，那么一定不会走回来了；否则，img一定会把整棵子树走完再回到当前点。

走到一个$s$到$t$路径上的点时，img会随机选择一个儿子走下去，这等价于随机一个儿子们的排列，然后按这个顺序走。

那么$s$到$t$的路径上所有点显然一定会走到，以$s$为根时$t$子树中的点显然走不到，而其它点都有$\frac 12$的概率会走到。

时间复杂度$O(nlogn+m)$。

prime：

$n$较小时，我们可以直接用线性筛/埃氏筛法求出每个数的最小质因数。

我们考虑进行容斥。对于每个质数$x$，我们需要求出$1$~$n/x$中不被比$x$小的质数整除的数的个数。一种简单的思路是，对于x<=k的情况，我们进行常见的枚举子集容斥；对于$x>k$的情况，$n/x$较小，我们就在$n/k$的范围内进行线性筛/埃氏筛法。

注意到进行子集容斥时，枚举子集后贡献形如$(-1)^i(n/S)$，而$n/S$只有$O(\sqrt n)$种取值，我们可以对这个进行记忆化。

时间复杂度$O(\frac{n^\frac34}{\sqrt {logn}})$

path：

这是课件里的例题。

点分治统计树上的情况，然后单独考虑经过剩下那条边的答案。

在环上按顺序枚举一个端点，用树状数组维护另一个端点到这条边的距离。

时间复杂度$O(nlogn)$。

以上是闫书弈大佬的题解

我的丑陋的代码(✿◡‿◡)：

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
#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
int a[500010], n, m, deep[500010], f[21][500010];
vector<int> v[500010];
int point;
void dfs(int x)
{
	for (int i = 1; i <= 20; ++i)
		f[i][x] = f[i - 1][f[i - 1][x]];
	a[x] = 1;
	for (int i = 0; i < v[x].size(); ++i)
		if (v[x][i] != f[0][x])
		{
			f[0][v[x][i]] = x;
			deep[v[x][i]] = deep[x] + 1;
			dfs(v[x][i]);
			a[x] += a[v[x][i]];
		}
}
int LCA(int x, int y)
{
	if (deep[x] < deep[y]) swap(x, y);
	if (deep[x] > deep[y])
	{
		for (int i = 20; ~i; --i)
			if (deep[x] - (1 << i) > deep[y]) x = f[i][x];
		if (f[0][x] == y)
		{
			point = x;
			return y;
		}
		x = f[0][x];
	}
	for (int i = 20; ~i; --i)
		if (f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];
	return f[0][x];
}
int main(int argc, char const *argv[])
{
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i < n; ++i)
	{
		int from = read(), to = read();
		v[from].push_back(to);
		v[to].push_back(from);
	}
	deep[1] = 1;
	dfs(1);
	while (m--)
	{
		int s = read(), t = read(), g, k;
		int lca = LCA(s, t);
		if (lca == t) k = n - a[point] - 1;
		else k = a[t] - 1;
		g = n + (deep[s] + deep[t] - 2 * deep[lca] + 1) - k;
		printf("%d.%d\n", g / 2, g % 2 * 5);
	}
	return 0;
}

Prime:

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
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull read()
{
	ull x = 0; char ch = 0;
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x;
}
const ull w = 1000;
int prime[5000000], cnt;
ull answer, n, k, sqr, s, c;
bool notprime[200000010];
ull g[510][8010];
ull fastpow(ull a, ull b = k)
{
	ull res = 1;
	// cerr<<"YEP"<<endl;
	while (b)
	{
		if (b & 1ull) res *= a;
		a *= a;
		b >>= 1ull;
	}
	// cerr<<"NOP"<<endl;
	return res;
}
ull f(ull N, int p)
{
	if (N <= 8000ull && g[p][N]) return g[p][N];
	ull res = N / prime[p];
	for (int i = 1; i < p; ++i)
	{
		if (1ull * prime[i]*prime[p] > N) break;
		res -= f(N / prime[p], i);
	}
	if (N <= 8000) g[p][N] = res;
	return res;
}
void Prime()
{
	notprime[1] = 1;
	for (int i = 2; i <= sqr; ++i)
	{
		if (!notprime[i]) prime[++cnt] = i;
		for (int j = 1; j <= cnt && 1ull * i * prime[j] <= sqr; ++j)
		{
			notprime[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
int main(int argc, char const *argv[])
{
	freopen("prime.in", "r", stdin);
	freopen("prime.out", "w", stdout);
	n = read(), k = read(), sqr = sqrt((long double)n);
	Prime();
	fill(notprime, notprime + sqr + 50, 0);
	s = n / w - 1;
	for (int i = 1; i <= cnt; ++i)
	{
		if ((ull)prime[i] <= w)
		{
			answer += (f(n, i) - 1) * fastpow(prime[i]);
		}
		else
		{
			for (ull j = n / prime[i] + 1; j <= c; ++j)
				if (!notprime[j]) --s;
			answer += s * fastpow(prime[i]);
		}
		// cerr<<"NOP"<<endl;
		if ((ull)prime[i] < w) c = n / w;
		else c = n / prime[i];
		for (ull j = prime[i]; j <= c; j += prime[i])
			if (!notprime[j]) notprime[j] = 1, --s;
	}
	printf("%llu", answer);
	return 0;
}

Path:

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
#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int N = 100010;
int tree[N << 2];
struct edge {
	int to, nxt;
} e[N << 1];
int linkk[N << 1], len(1), pos, bit[N], check[N], fa[N];
int n, m, c, Pathcnt, k;
long long ans;
void insert(int u, int v)
{
	e[++len].to = v, e[len].nxt = linkk[u], linkk[u] = len;
	e[++len].to = u, e[len].nxt = linkk[v], linkk[v] = len;
	check[len - 1] = check[len] = 1;
}
int lowbit(int x)
{
	return x & -x;
}
void change(int x, int flag)
{
	if (flag == 1)
		while (x <= n)
		{
			if (tree[x] != pos) tree[x] = pos, bit[x] = 1;
			else ++bit[x];
			x += lowbit(x);
		}
	else
		while (x <= n)
		{
			--bit[x];
			x += lowbit(x);
		}
}
long long sum(int x)
{
	if (x < 0) return 0;
	int ans = 0;
	while (x)
	{
		if (tree[x] == pos) ans += bit[x];
		x -= lowbit(x);
	}
	return ans;
}
int getfa(int x)
{
	return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
int size[N], max_part[N];
int tot, now_root, deep[N], to[N];
int Path_[N];
bool vis[N], is_main[N];
int point_u, point_v;
void getroot(int x, int fa)
{
	size[x] = 1; max_part[x] = 0;
	for (int i = linkk[x]; i; i = e[i].nxt)

	{
		int to = e[i].to;
		if (to == fa || !check[i]) continue;
		getroot(to, x);
		size[x] += size[to];
		max_part[x] = max(max_part[x], size[to]);
	}
	max_part[x] = max(max_part[x], tot - size[x]);
	if (max_part[now_root] > max_part[x]) now_root = x;
}
void Ncalc(int x, int fa, int dep)
{
	ans += sum(n) - sum(k - dep - 1);
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		if (!check[i] || e[i].to == fa) continue;
		Ncalc(e[i].to, x, dep + 1);
	}
}
void Nadd(int x, int fa, int dep)
{
	change(dep + 1, 1);
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		if (!check[i] || e[i].to == fa) continue;
		Nadd(e[i].to, x, dep + 1);
	}
}
void FindPath(int x, int fa, int dep)
{
	to[x] = fa, deep[x] = dep;
	change(deep[x], 1);
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		if (e[i].to == fa) continue;
		FindPath(e[i].to, x, dep + 1);
	}
}
void solve(int x)
{
	++pos;
	change(1, 1);
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		if (!check[i]) continue;
		Ncalc(e[i].to, x, 1);
		Nadd(e[i].to, x, 1);
	}
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		if (!check[i]) continue;
		check[i ^ 1] = 0;
		max_part[0] = tot = size[e[i].to];
		now_root = 0;
		getroot(e[i].to, 0);
		solve(now_root);
	}
}
void del_on_tree(int x, int fa)
{
	change(deep[x], -1);
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		if (e[i].to == fa || is_main[e[i].to]) continue;
		del_on_tree(e[i].to, x);
	}
}
void calc_on_tree(int x, int fa, int dep)
{
	ans += sum(n) - sum(k - dep - 1);
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		if (e[i].to == fa || is_main[e[i].to]) continue;
		calc_on_tree(e[i].to, x, dep + 1);
	}
}
int main()
{
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	n = read(), m = read(), k = read();
	for (int i = 1; i <= n; ++i) fa[i] = i;
	for (int i = 1; i <= m; ++i)
	{
		int u = read(), v = read();
		if (getfa(u) == getfa(v)) point_u = u, point_v = v;
		else fa[fa[u]] = fa[v], insert(u, v);
	}
	now_root = 0, max_part[now_root] = tot = n;
	getroot(1, 0);
	solve(now_root);
	if (point_u)
	{
		++pos; FindPath(point_u, 0, 1);
		for (int i = point_v; i; i = to[i]) Path_[++Pathcnt] = i, is_main[i] = 1;
		for (int i = 1; i < Pathcnt; ++i)
		{
			del_on_tree(Path_[i], 0);
			calc_on_tree(Path_[i], 0, i);
		}
	}
	printf("%lld", ans);
	return 0;
}

小福利

数据下载请戳我(*╹▽╹*) (Click Me For data.rar)

-------------本文结束(づ￣ 3￣)づ~感谢您的阅读(*╹▽╹*)-------------