https://ac.nowcoder.com/acm/contest/10845

E - 牛牛数数

 

题意:给定 n 个数字,用其中任意一个非空子集的异或和得到数字 x,问有多少种 x 大于给定数 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
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
#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;
struct Linear_Basis
{
ll b[63], nb[63], tot, len;

void init()
{
tot = 0;
len = 0;
memset(b, 0, sizeof(b));
memset(nb, 0, sizeof(nb));
}

bool ins(ll x)//插入
{
for (int i = 62; i >= 0; i--)
if (x&(1ll << i))
{
if (!b[i]) { b[i] = x; len++; break; }
x ^= b[i];
}
return x > 0;
}

ll Max()//所有可能异或中最大
{
ll res = 0;
for (int i = 62; i >= 0; i--)
res = max(res, res^b[i]);
return res;
}

ll Min()//所有可能异或中最小
{
for (int i = 0; i <= 62; i++)
if (b[i]) return b[i];
return -1;
}

void rebuild()
{
tot = 0;
for (int i = 62; i >= 0; i--)
for (int j = i - 1; j >= 0; j--)
if (b[i] & (1ll << j)) b[i] ^= b[j];
for (int i = 0; i <= 62; i++)
if (b[i]) nb[tot++] = b[i];
}

ll Kth_Max(ll k) //所有可能异或中k小
{
ll res = 0;
for (int i = 62; i >= 0; i--)
if (k&(1ll << i)) res ^= nb[i];
return res;
}

} LB;
int n;
ll K;
ll a[N];
int main() {
scanf("%d%lld", &n, &K);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
LB.ins(a[i]);
}
ll mx = LB.Max();
ll mn = LB.Min();
if (mx <= K) { puts("0"); return 0; }
if (mn > K) { printf("%lld\n", n); return 0; }
ll L = 1, R = (1ll << LB.len);
LB.rebuild();
while (L < R) {
ll mid = (L + R + 1) / 2;
ll x = LB.Kth_Max(mid);
if (x <= K)L = mid;
else R = mid - 1;
}
printf("%lld\n", (1ll << LB.len) - 1 - L);
return 0;
}

 

F - phi and phi

 

题意:定义 ans(n)=\sum_\limits{i=1}^n\sum\limits_{j=1}^n\phi(ij)\phi(\gcd(i,j))。给定 NN,求 ans(1),ans(2),,ans(N)ans(1),ans(2),\cdots,ans(N)

莫比乌斯反演+差分前缀和

ϕ(n)=n(11p1)(11p2)(11pk)\phi(n)=n\cdot(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})\\

所以展开能得到

ϕ(ij)=ϕ(i)ϕ(j)ϕ(gcd(i,j))gcd(i,j)\phi(ij)=\frac{\phi(i)\phi(j)}{\phi(\gcd(i,j))}\cdot\gcd(i,j)\\

i=1nj=1nϕ(ij)ϕ(gcd(i,j))=i=1nj=1nϕ(i)ϕ(j)gcd(i,j)=d=1ndi=1n/dj=1n/dϕ(id)ϕ(jd)[gcd(i,j)=1]=d=1ndi=1n/dj=1n/dϕ(id)ϕ(jd)kgcd(i,j)μ(k)=d=1ndk=1n/dμ(k)i=1n/(dk)j=1n/(dk)ϕ(idk)ϕ(jdk)=d=1ndk=1n/dμ(k)(i=1n/(dk)ϕ(idk))2\begin{align} &\sum_{i=1}^n\sum_{j=1}^n\phi(ij)\phi(\gcd(i,j))\\ &=\sum_{i=1}^n\sum_{j=1}^n\phi(i)\phi(j)\gcd(i,j)\\ &=\sum_{d=1}^n d\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\phi(id)\phi(jd)[\gcd(i,j)=1]\\ &=\sum_{d=1}^n d\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\phi(id)\phi(jd)\sum_{k|\gcd(i,j)}\mu(k)\\ &=\sum_{d=1}^n d\sum_{k=1}^{n/d}\mu(k)\sum_{i=1}^{n/(d\cdot k)}\sum_{j=1}^{n/(d\cdot k)}\phi(idk)\phi(jdk)\\ &=\sum_{d=1}^n d\sum_{k=1}^{n/d}\mu(k)(\sum_{i=1}^{n/(d\cdot k)}\phi(idk))^2\\ \end{align}

T=dkT=d\cdot k,变换求和顺序,可以想象到对于每一组 (d,k)(d,k) 可以一一对应于 (T,d)(T,d)

=T=1ndTdμ(Td)(i=1n/Tϕ(iT))2\begin{align} &=\sum_{T=1}^n\sum_{d|T}d\cdot\mu(\frac{T}{d})(\sum_{i=1}^{n/T}\phi(i\cdot T))^2\\ \end{align}

由于有迪利克雷卷积公式 ϕ=IDμ\phi=ID*\mu,所以

=T=1nμ(T)(i=1n/Tϕ(iT))2=\sum_{T=1}^{n}\mu(T)(\sum_{i=1}^{n/T}\phi(i\cdot T))^2\\

换一下符号看得清楚点

最终

ans(n)=d=1nμ(d)(i=1n/dϕ(id))2ans(n)=\sum_{d=1}^{n}\mu(d)(\sum_{i=1}^{n/d}\phi(i\cdot d))^2\\

接下来枚举 dd

在固定 dd 的情况下,dd 对每一个 nn 的贡献如下图

对每个区间的贡献相同,所以差分做。

其中有 O(n/d)O(n/d) 个区间,dd11nn,所以复杂度为 O(nlogn)O(n\log 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
#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;
int prime[N], vis[N], tot, phi[N];
void pre(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[tot++] = i;
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) {
phi[d] = phi[i] * prime[j];
break;
}
else phi[d] = phi[i] * phi[prime[j]];
}
}
}
ll ans[N];
int main() {
scanf("%d", &n);
pre(n);
for (int d = 1; d <= n; d++) {
ll sum = 0;
for (int i = 1; i <= n / d; i++) {
sum = (sum + phi[i*d]) % mod;
int L = i * d, R = min((i + 1)*d, n + 1);
ans[L] = (ans[L] + sum * sum%mod*phi[d] % mod) % mod;
ans[R] = (ans[R] - sum * sum%mod*phi[d] % mod + mod) % mod;
}
}
for (int i = 2; i <= n; i++)ans[i] = (ans[i] + ans[i - 1]) % mod;
for (int i = 1; i <= n; i++)printf("%lld\n", ans[i]);
return 0;
}

 

D - 魔物消灭计划

 

题意:给定一张带边权的无向图,一些点上有宝石,共有 k 种宝石,有相同宝石的点之间可以无代价传送,否则走相邻点,代价为边权。现在要使得起点 x,终点 y,以及一个至少包含 k 种宝石的点集连通,问最小代价。

斯坦纳树

比较模板的斯坦纳树题。

需要注意的是相同颜色的点要特殊处理,要么连成边权为零的团,要么求spfa的时候单独处理。

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
#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, m, k, x, y;
struct E
{
int v, w;
};
vector<E>G[N];
int col[N], a[N], tot, dp[2020][110];
typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, greater<pii> >q;
void dij(int* d) {
while (!q.empty()) {
int u = q.top().second, di = q.top().first; q.pop();
if (di > d[u])continue;
for (E& e : G[u]) {
int v = e.v, w = e.w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({ d[v],v });
}
}
}
}
vector<int>vc[110];
int main() {
scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);
tot = k;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i])vc[a[i]].push_back(i);
}
a[x] = ++k;
a[y] = ++k;
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
if (a[u] == a[v] && a[u])continue;
G[u].push_back({ v,w });
G[v].push_back({ u,w });
}
for (int i = 1; i <= k; i++) {
for (int j = 0; j < (int)vc[i].size(); j++) {
for (int k = j + 1; k < (int)vc[i].size(); k++) {
G[vc[i][j]].push_back({ vc[i][k],0 });
G[vc[i][k]].push_back({ vc[i][j],0 });
}
}
}
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) {
if (a[i] != 0) {
dp[1 << (a[i] - 1)][i] = 0;
}
}
for (int s = 0; s < (1 << k); s++) {
for (int i = 1; i <= n; i++) {
for (int t = (s - 1)&s; t; t = (t - 1)&s) {
dp[s][i] = min(dp[s][i], dp[t][i] + dp[s^t][i]);
}
if (dp[s][i] != INF)q.push({ dp[s][i],i });
}
dij(dp[s]);
}
printf("%d\n", dp[(1 << k) - 1][x]);
return 0;
}