avatar

zhengrui contest 609

这场成绩看上去可以,其实是打的很糟糕的一场比赛。

这场比赛用到的套路:

1.1.动态插入删除线性基以及一类离线后维护删除时间较晚的问题

2.2.对每个质数单独考虑,可能能解决形如gcd\prod{gcd}的问题

3.3.x\sqrt{x}分类讨论,甚至x3\sqrt[3]{x}


A

要维护插入和删除的线性基,普通的方法自然是线段树合并。至于O(nq)O(nq)的正解,把套路记住就行了。

方法就是,维护每个数出现时间,尽可能先删除删除时间早的

还有一个例子就是动态维护图连通性。朴素也是线段树分治和并茶集。那么,倘若维护了边权是删除时间最大生成树,复杂度就能变成O(nlogn)O(nlogn)

至于具体怎么实现,看看代码很容易理解。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define getchar() (*input_pos++)
const int TT = 20 * 2e6;
char input_buffer[TT];
char *input_pos = input_buffer;
inline int getint() {
int x = 0, p = 1; char c = getchar();
while (c <= 32) c = getchar();
if (c == 45) p = -p, c = getchar();
while (c > 32) x = x * 10 + c - 48, c = getchar();
return x * p;
}
using namespace std;
//ruogu_alter
const int N = 2e6 + 5;
int n, q, res, c;
int to[N], val[N], pos[N], id[N];
int b[30], tim[30];
inline int ins(int x, int t) {
if (!x) return 0;
for (int i = n - 1; i >= 0; i--) if (x >> i & 1) {
if (!b[i]) { b[i] = x; tim[i] = t; return 1; }
else {
if (tim[i] < t) { swap(tim[i], t); swap(b[i], x); }
x ^= b[i];
}
}
return 0;
}
inline int del(int t) {
for (int i = n - 1; i >= 0; i--) if (tim[i] == t) {
tim[i] = -1; b[i] = 0;
return 1;
}
return 0;
}
//
int main() {
fread(input_buffer, 1, TT, stdin);
n = getint(); q = getint();
memset(to, -1, sizeof(to));
memset(tim, -1, sizeof(tim));
rep(i, q) {
int op = getint(), x = val[i] = getint();
if (op == 1) {
id[c++] = x;
to[i] = q;
}
}
sort(id, id + c);
c = unique(id, id + c) - id;
rep(i, q) {
if (to[i] >= 0) {
pos[lower_bound(id, id + c, val[i]) - id] = i;
}
else {
to[pos[lower_bound(id, id + c, val[i]) - id]] = i;
}
}
int sz = 0;
rep(qq, q) {
if (to[qq] >= 0) sz += ins(val[qq], to[qq]);
else sz -= del(qq);
res ^= (1 << n - sz);
}
cout << res << endl;
return 0;
}

B​

这题可以先写个暴力的dpdp,算出来的其实是贝尔数。。n=12n=12的时候,贝尔数是不大的,大概41064*10^6。这时就可以写一个暴力程序了。。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
int x = 0, p = 1; char c = getchar();
while (c <= 32) c = getchar();
if (c == 45) p = -p, c = getchar();
while (c > 32) x = x * 10 + c - 48, c = getchar();
return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 20;
const int M = (1 << 15) + 5;
int n, m, e[N], msk[N], mn[M], a[N], res, lim;
//
inline int calc(vector<int> &v) {
sort(v.begin(), v.end());
int ans = v.size();
rep(i, v.size()) ans = mul(ans, v[i] - i + 1);
return ans;
}
void dfs(int x, int c) {
if (x == n) {
vector<int> v;
rep(i, c + 1) v.emplace_back(mn[msk[i]]);
reduce(res += calc(v) - mod);
return;
}
rep(i, c + 2) if (!(msk[i] & e[x])) {
msk[i] |= (1 << x);
dfs(x + 1, max(c, i));
msk[i] ^= (1 << x);
}
}
void dfs2(int x) {
if (x == n) {
rep(i, lim + 1) reduce(res += (msk[i] > 0) - mod);
return;
}
rep(i, a[x] + 1) if (!(msk[i] & e[x])) {
msk[i] |= (1 << x);
dfs2(x + 1);
msk[i] ^= (1 << x);
}
}
int main() {
n = getint(); m = getint();
rep(i, n) {
a[i] = getint();
lim = max(lim, a[i]);
}
rep(mask, 1 << n) {
mn[mask] = INF;
rep(i, n) if (mask >> i & 1) mn[mask] = min(mn[mask], a[i]);
}
rep(i, m) {
int x = getint() - 1, y = getint() - 1;
e[x] |= (1 << y); e[y] |= (1 << x);
}
if (lim <= 2) {
dfs2(0);
cout << res << endl;
return 0;
}
if (m == n * (n - 1) / 2) {
vector<int> v;
rep(i, n) v.emplace_back(a[i]);
printf("%d\n", calc(v));
return 0;
}
dfs(0, -1);
cout << res << endl;
return 0;
}

这个有7979,分数其实非常实惠,如果正式考试的话应该这样写是不错的选择。但是其实再多想几分钟,就能直接发现正解,就是O(n3n)O(n3^n)dp[S][x]dp[S][x]表示已经集合SS已经选了xx个相等的方案数。为了方便统计,我们要尽可能把当前未在集合里aa最小的划进来。

http://zhengruioi.com/submission/228619

留个坑,看看桌面上的论文。。

留个坑,看看子集卷积。。http://zhengruioi.com/submission/227500


C

对于这一类gcdgcd的问题那么自然要看看

1.1.容斥

2.2.形如对区间的dpdp

3.3.对每个质数单独考虑

就这题而言,那当然需要的诀窍正是:对每个质数单独考虑!!!

现在我们考虑插入一个数xx,他对现有集合的贡献是

pkxp^k|x,贡献就是p2cnt[pk]1p^{2^{ cnt[p^k]-1}}

然后对每个pkxp^k|xcnt[pk]+1cnt[p^k] +1

自然要莫队。先是O(nqlogwlogw)O(n\sqrt{q}logwlogw),大抵因为既要分解质因数,又要快速米;然后想办法把快速幂去掉;然后就是精彩的套路。

一个数大于w\sqrt{w}的质因数只有一个!这个可以直接O(1)O(1)插入。

至于所有pwp \leq \sqrt{w}pk<wp^k<w,这样的所有ppk\sum{k}只有O(wlogw)O(\frac{\sqrt{w}}{logw})!!震撼全场!

也就是说对于所有pwp \leq \sqrt{w},我们都可以不用莫队而是直接在静态数组上用前缀和O(wlogw)O(\frac{\sqrt{w}}{logw})求答案!

总复杂度nqn\sqrt{q}


文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/05/02/zhengrui-contest-609/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog

评论