https://ac.nowcoder.com/acm/contest/10743
D - Lots of Edges
题意：给定 n 个点，有点权 ai，若 ai&aj=0，则点 i,j 连一条边权为 1 的边，给定起点 S，问从 S 到每个点的最短路。
枚举子集+bfs
重新建图，把原图上点权相同的点缩成一个点，则每一条边的两个端点都有二进制下的子集关系，则总边数是 O(3k)。再bfs求最短路。
要注意点权和起点相同的点要在最后特殊处理。以及枚举子集时不要忘了0.
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
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, s;
int a[N], d[N], vis[N], cnt[N];
void bfs(int s) {
queue<int>q;
q.push(s);
memset(d, 0x3f, sizeof(d));
d[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (vis[u] || !cnt[u])continue;
vis[u] = 1;
int t = (131071 ^ u);
for (int v = t; v; v = (v - 1)&t) {
if (!vis[v] && cnt[v]) {
d[v] = min(d[v], d[u] + 1);
q.push(v);
}
}
if (!vis[0] && cnt[0]) {
d[0] = min(d[0], d[u] + 1);
q.push(0);
}
}
}
int main() {
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
bfs(a[s]);
d[a[s]] = INF;
int t = (131071 ^ a[s]);
for (int v = t; v; v = (v - 1)&t) {
if (cnt[v])d[a[s]] = min(d[a[s]], d[v] + 1);
}
if (cnt[0])d[a[s]] = min(d[a[s]], d[0] + 1);
if (a[s] == 0)d[a[s]] = 1;
for (int i = 1; i <= n; i++) {
printf("%d%c", i == s ? 0 : (d[a[i]] == INF ? -1 : d[a[i]]), " \n"[i == n]);
}
return 0;
}
|
F - 简单题
题意：给定 n,m，求 i=1∑nj=1∑mgcd(i,j)φ(ij)μ(ij).
莫比乌斯反演+迪利克雷后缀和
第一个关键点在于有贡献的 i,j 一定是互质的，否则 μ(ij)=0.
因此积性函数 φ 和 μ 可以拆开了。
所以变成
=i=1∑nj=1∑mφ(i)φ(j)μ(i)μ(j)[gcd(i,j)=1]
再莫比乌斯反演
=d=1∑min(n,m)μ(d)(i=1∑⌊dn⌋μ(id)φ(id))(i=1∑⌊dm⌋μ(id)φ(id))
这样暴力枚举复杂度是 O(nlogn)，会T。
用迪利克雷后缀和。
迪利克雷后缀和用于求 bi=i∣j∧j≤n∑aj.
原理大致是，若数字 j 等于 i 乘一个质数，则从 j 连一条指向 i 的边，对每个点求它的祖先的 a 之和。所以可以通过按照拓扑序枚举，以前缀和的形式求。
参考 https://blog.csdn.net/weixin_45697774/article/details/111052242
复杂度 O(nloglogn).
本题先变成
=d=1∑min(n,m)μ(d)(d∣i∧i≤n∑μ(i)φ(i))(d∣i∧i≤m∑μ(i)φ(i))
再套迪利克雷后缀和。
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
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n, m;
unsigned int mu[N], phi[N], vis[N], prime[N], tot;
void pre(int n) {
mu[1] = phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[tot++] = i;
mu[i] = -1;
phi[i] = i - 1;
}
ll d;
for (int j = 0; j < tot && (d = i * prime[j]) <= n; j++) {
vis[d] = 1;
if (i%prime[j] == 0) {
mu[d] = 0;
phi[d] = phi[i] * prime[j];
break;
}
else {
phi[d] = phi[i] * phi[prime[j]];
mu[d] = mu[i] * mu[prime[j]];
}
}
}
}
unsigned int a[N], b[N];
int main() {
pre(20000000);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)a[i] = mu[i] * phi[i];
for (int i = 1; i <= m; i++)b[i] = mu[i] * phi[i];
for (int i = 0; i < tot && prime[i] <= n; i++) {
for (int j = n / prime[i]; j; j--) {
a[j] += a[j*prime[i]];
}
}
for (int i = 0; i < tot && prime[i] <= m; i++) {
for (int j = m / prime[i]; j; j--) {
b[j] += b[j*prime[i]];
}
}
unsigned int ans = 0;
for (int d = 1; d <= min(n, m); d++) {
unsigned int t1 = 0, t2 = 0;
ans += mu[d] * a[d] * b[d];
}
printf("%u\n", ans);
}
return 0;
}
|
