暑假集训 杭电多校 Round 5

题目链接

补题链接

「1001」 Typhoon

签到题，遍历每条线段到每个点的最小距离即可。

时间复杂度：\(O(mn)\)

空间复杂度：\(O(m)\)

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
#include <iostream>
#include <cstdio>
#include <cmath>

struct Point {
    double x, y;
};

inline double dist2(const Point& p1, const Point& p2) {
    double dx = (p1.x - p2.x);
    double dy = (p1.y - p2.y);

    return dx * dx + dy * dy;
}

double dist2line(const Point& p0, const Point& p1, const Point& p2) {
    double vx = p2.x - p1.x, vy = p2.y - p1.y;
    double d1 = vx * (p1.x - p0.x) + vy * (p1.y - p0.y);
    double d2 = vx * (p2.x - p0.x) + vy * (p2.y - p0.y);

    if (d1 * d2 < 0) {
        double f1 = (p2.x - p1.x) * (p0.y - p1.y) - (p2.y - p1.y) * (p0.x - p1.x);
        double f2 = (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);

        return f1 * f1 / f2;
    }
    else {
        return std::min(dist2(p0, p1), dist2(p0, p2));
    }
}

#define MAX_N 10005

Point pos[MAX_N];

void solve() {
    int m, n;
    std::cin >> m >> n;
    for (int i = 0; i < m; i++) {
        std::cin >> pos[i].x >> pos[i].y;
    }
    Point p0; // 庇护所
    for (int i = 0; i < n; i++) {
        std::cin >> p0.x >> p0.y;
        double res = INFINITY;
        for (int i = 1; i < m; i++) {
            res = std::min(res, dist2line(p0, pos[i - 1], pos[i]));
        }
        printf("%.4lf\n", std::sqrt(res));
    }
}

int main() {

    solve();

    return 0;
}

「1002」 GCD Magic

首先，显然有 \(gcd(2 ^ i - 1, 2 ^ j - 1)\) = \(2 ^ {gcd(i, j)} - 1\) ，所以原表达式只与 \(gcd(i, j)\) 有关，所以我们只用枚举全部 \(i\) 和 \(j\) 的最大公约数的数量即可。

对于 \(i、j\) 满足 \(1 \leq i、j \leq n\) 而言，满足 \(gcd(i, j) = t\) 的数量为： \[ \begin{array}{} \sum_{i = 1} ^ n \sum_{j = 1} ^ n [gcd(i, j) = t] \\ = \sum_{i = 1} ^ {[\frac{n}{t}]} \sum_{j = 1} ^ {[\frac{n}{t}]} [gcd(i, j) = 1] \\ = \sum_{i = 1} ^ {[\frac{n}{t}]} \sum_{j = 1} ^ {[\frac{n}{t}]} \sum_{d | gcd(i, j)} \mu(d) \\ = \sum_{d = 1} ^ {[\frac{n}{t}]} \mu(d) \sum_{i = 1} ^ {[\frac{n}{t}]} \sum_{j = 1} ^ {[\frac{n}{t}]} [d | gcd(i, j)] \\ = \sum_{d = 1} ^ {[\frac{n}{t}]} \mu(d) [\frac{n}{td}] ^ 2 \end{array} \] 要计算的表达式可化为 \(f(t) = (2 ^ t - 1) ^ k\) ，因此最终要求的表达式如下所示： \[ \sum_{t = 1} ^ n f(t) \sum_{d = 1} ^ {[\frac{n}{t}]} \mu(d) [\frac{n}{td}] ^ 2 \] 令 \(T = dt\) ，交换求和顺序，先枚举 \(T\) ，上式可转化为： \[ \sum_{T = 1} ^ n [\frac{n}{T}] ^ 2 \sum_{d | T} f(d) \mu(\frac{T}{d}) \] 由于题目中的 \(n\) 很大，所以这里考虑使用杜教筛来计算 \(\sum_{d | T} f(d)\mu(\frac{T}{d})\) 的前缀和，然后使用分块除法来快速求出上式的值。

考虑狄利克雷卷积，\(f * \mu * 1 = f * \epsilon = f(T)\) ，设 \(S(n) = \sum_{T = 1} ^ n \sum_{d | T} f(d) \mu(\frac{T}{d})\) 则有： \[ S(n) = \sum_{T = 1} ^ n f(T) - \sum_{d = 2} ^ n S([\frac{n}{d}]) \]

\[ f(T) = (2 ^ T - 1) ^ K = \sum_{i = 0} ^ K C_{K} ^ i 2 ^ {Ti} (-1) ^ {K - i} \]

此处就是一个等比数列求和。

时间复杂度：\(O(K \sqrt n)\)

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
#include <cmath>
#include <cstdio>
#include <unordered_map>
using namespace std;
using LL = long long;
const int maxs = 1000001, maxk = 10, MOD = 998244353;

int te, K;
LL n;
int u[maxs + 5], p[maxs + 5];
bool pri[maxs + 5];
int C[maxk + 5][maxk + 5], val[maxk + 5];
int lim, G[maxs + 5];
unordered_map<LL, int> f;
int ans;

inline int ADD(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
inline int MUL(int x, int y) { return (LL)x * y % MOD; }
int Pow(int w, int b) {
	int s;
	for (s = 1; b; b >>= 1, w = MUL(w, w))
		if (b & 1)
			s = MUL(s, w);
	return s;
}
void Make() {
	for (int i = 0; i <= maxk; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++)
			C[i][j] = ADD(C[i - 1][j - 1], C[i - 1][j]);
	}
	for (int i = 1; i <= maxk; i++)
		val[i] = MUL(1 << i, Pow((1 << i) - 1, MOD - 2));
	u[1] = 1;
	for (int i = 2; i <= maxs; i++) {
		if (!pri[i])
			p[++p[0]] = i, u[i] = MOD - 1;
		for (int j = 1, t; j <= p[0] && (t = i * p[j]) <= maxs; j++) {
			pri[t] = true;
			if (i % p[j])
				u[t] = (MOD - u[i]) % MOD;
			else {
				u[t] = 0;
				break;
			}
		}
	}
}
int SumF(LL n) {
	int ans = MUL(K & 1 ? MOD - 1 : 1, n % MOD);
	int BA = Pow(2, n % (MOD - 1)), pw = BA;
	for (int j = 1; j <= K; j++) {
		int now = MUL(C[K][j], K - j & 1 ? MOD - 1 : 1);
		now = MUL(now, MUL(val[j], ADD(pw, MOD - 1)));
		ans = ADD(ans, now);
		pw = MUL(pw, BA);
	}
	return ans;
}
int Sum(LL n) {
	if (n <= lim)
		return G[n];
	if (f.count(n))
		return f[n];
	int ans = SumF(n);
	for (LL l = 2, r; l <= n; l = r + 1) {
		r = n / (n / l);
		ans = ADD(ans, MOD - MUL(Sum(n / l), (r - l + 1) % MOD));
	}
	return f[n] = ans;
}
int main() {
	Make();
	for (scanf("%d", &te); te; te--) {
		scanf("%lld%d", &n, &K);
		lim = pow(n, 2.0 / 3) + 1;
		for (int i = 1; i <= lim; i++)
			G[i] = 0;
		for (int i = 1, pw = 2; i <= lim; i++, pw = MUL(pw, 2)) {
			int F = Pow(pw - 1, K);
			for (int j = i, k = 1; j <= lim; j += i, k++)
				G[j] = ADD(G[j], MUL(u[k], F));
		}
		for (int i = 1; i <= lim; i++)
			G[i] = ADD(G[i], G[i - 1]);
		f.clear();
		ans = 0;
		for (LL l = 1, r; l <= n; l = r + 1) {
			r = n / (n / l);
			ans = ADD(ans, MUL(ADD(Sum(r), MOD - Sum(l - 1)), MUL(n / l % MOD, n / l % MOD)));
		}
		printf("%d\n", ans);
	}
	return 0;
}
ACM
#杭电多校
暑假集训 杭电多校 Round 5
https://goer17.github.io/2023/08/01/暑假集训 杭电多校 Round 5/
作者
Captain_Lee
发布于
2023年8月1日
许可协议