A/B
弱智题目。半小时写不完的应该加训简单Div.2 adhoc。
C
题目大意:给定一个数组 $a_1,a_2,\ldots,a_n$ ,请求出对于任意 $l \lt r$ , $(a_l \& m) \oplus (a_{l+1} \& m) \ldots \oplus (a_r \& m)$ 的最大值,其中 $m=\max(a_l,a_{l+1},\ldots,a_r)$ 。
数据范围: $2 \leq \sum n \leq 2 \cdot 10^5,0 \leq a_i \lt 2^{18}$
思路:本题赛时想到了思路但未通过,原因比较搞笑,赛后补了。
可以看出,原式可以化简为 $(a_l \oplus a_{l+1} \ldots a_r) \& m$ ,从而可以化简出前缀和的形式,即 $(pre_{r} \oplus pre_{l-1}) \& m$ 。
然后,思考一下,最大值的处理很棘手,可以通过什么方法来做?想必看到异或和最大,很容易想到什么,字典树上启发式合并之类的东西,但是这样没有办法处理最大值,于是经过漫长的思考之后,想起了还有笛卡尔树分治这种东西。
那么,笛卡尔树分治中,最大值显而易见地被确定为了当前根节点,然后按照短边进行分治,然后同时,注意到这里的 $r$ 跟 $l-1$ 之间的距离至少为 $2$ ,这里也很难考虑,怎么办?
可能这个时候会想到, $pre_{r} \oplus pre_{l-1}$ 必然是 $m$ 的子集,但是枚举子集显然会爆复杂度,又一看需要求最大值,很自然地考虑高位到低位贪心的试填法,从而只需要考虑如何 check 当前位是否能为 1。
那么,就是 $(pre_{r} \& x) \oplus (pre_{l-1} \& x)$ 了,这题 $x$ 为当前试填的值。也就是说,对于每次 $check$ 的时候,可以预处理 $pre_i \& x$ ,然后,只需要考虑 $r \gt l-1$ 这一个点,而此时完全可以离线处理每个 $l$ 或者 $r$ 对应的询问,例如,当左边比较短的时候,考虑左边的 $l$ ,那么我们需要查询 $\max(j,l+1) \leq r \leq R,(pre_r \& x) =(pre_{l-1} \& x) \oplus x$ 对应的 $r$ 是否存在,这里 $[L,R]$ 表示当前笛卡尔树区间, $j$ 为最大值位置,然后把询问挂在 $R$ 上,对于所有可能的 $l$ ,查询是否有 $las_{(pre_{l-1} \& x) \oplus x} \geq \max(j,l+1)$ ,注意此时需要考虑 $m$ 是否与 $x$ 存在包含关系。
当右边比较短的时候,则考虑枚举 $r$ ,此时需要找到 $l-1$ 满足 $L-1 \leq l-1 \leq \min(j-1,r-2),(pre_{l-1} \& x) =(pre_{r} \& x) \oplus x$ ,而发现,当 $r = j$ 时,把询问挂到 $j-2$ 上,然后看是否 $las_{(pre_j \& x) \oplus x} \geq L-1$ ,当 $r \gt j$ 时,则把查询挂到 $L-1$ 上,只需查询是否有 $las_{(pre_r \& x) \oplus x} \geq L-1$ ,此时把询问挂到 $j-1$ 上。
然后最搞笑的地方是,赛时每次 check 时,都使用了ranges::fill(las,-1),然后就爆了,为了减少常数,需要对las每次打上时间戳,来检查它是否可用,这个思路比较少见,整道题的时间复杂度为 $O(n \log n \log V)$ 。
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
| // 笛卡尔树,默认为大根堆
template <class T, typename Compare = std::greater<T>>
struct CartesianTree {
T inf = std::numeric_limits<T>::max();
struct Node {
int idx; // 原数组下标
T val; // 权值
int par, siz; // 父节点索引,子树大小
std::array<T, 2> son; // 左儿子,右儿子
Node(int idx = 0, T val = 0, int par = 0, int siz = 0) : idx(idx), val(val), par(par), siz(siz), son{} {}
};
std::vector<Node> t;
CartesianTree() { init(); }
void init(Compare comp = Compare()) {
t.assign(1, {0, 0, 0});
t[0].son.fill(0);
if (comp(-inf, inf))
t[0].val = -inf;
else
t[0].val = inf;
} // 自动建立虚拟节点
void add(int idx, T val, int par = 0) { t.emplace_back(idx, val, par); } // 负责把元素加进末尾,需要使用1-based
int work(Compare comp = Compare()) {
for (int i = 1; i < t.size(); i++) {
int k = i - 1;
while (comp(t[i].val, t[k].val)) k = t[k].par;
t[i].son[0] = t[k].son[1];
t[k].son[1] = i;
t[i].par = k;
t[t[i].son[0]].par = i;
} // 遍历,砍树枝
auto dfs = [&](auto&& dfs, int u) -> void {
if (!u) return;
t[u].siz = 1;
dfs(dfs, ls(u));
dfs(dfs, rs(u));
t[u].siz += t[ls(u)].siz + t[rs(u)].siz;
}; // 进行一个dfs
dfs(dfs, t[0].son[1]);
return t[0].son[1];
}
int Left(int p) { return p - size(ls(p)); } // 左边最远
int Right(int p) { return p + size(rs(p)); } // 右边最远
int size(int p) { return t[p].siz; }
int ls(int p) { return t[p].son[0]; }
int rs(int p) { return t[p].son[1]; }
int par(int p) { return t[p].par; }
};
/* 使用示例
CartesianTree<int, less<int>> ct;
rep(i, 0, n - 1) { ct.add(i + 1, nums[i]); }
int root = ct.work(less<int>());
rep(i, 1, n) {
int L = ct.Left(i);
int R = ct.Right(i);
}
*/
const ll MX = 1LL << 18;
ll las[MX];
ll tag[MX];
ll tim = 0;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl pre(n + 1);
rep(i, 1, n) pre[i] = pre[i - 1] ^ a[i - 1];
CartesianTree<ll> ct;
rep(i, 0, n - 1) ct.add(i + 1, a[i]);
ct.work();
vl l(n + 1), r(n + 1);
vvl queries(n + 1);
vector<bool> vis(n + 1, false);
rep(i, 1, n) {
l[i] = ct.Left(i), r[i] = ct.Right(i);
if (i - l[i] + 1 <= r[i] - i + 1)
queries[r[i]].emplace_back(i);
else
vis[i] = true;
}
auto check = [&](ll x) -> bool {
tim++;
vl pre2(n + 1);
rep(i, 0, n) pre2[i] = (pre[i] & x);
rep(i, 0, n) {
tag[pre2[i]] = tim;
las[pre2[i]] = i;
for (auto& j : queries[i]) {
if ((a[j - 1] & x) != x) continue;
rep(v, l[j] - 1, j - 1) {
ll l1 = max(j, v + 2);
if (l1 > i) continue;
if (tag[pre2[v] ^ x] == tim && las[pre2[v] ^ x] >= l1) return true;
}
}
if (i + 2 <= n && vis[i + 2] && ((a[i + 1] & x) == x)) {
if (l[i + 2] - 1 <= i && tag[pre2[i + 2] ^ x] == tim && las[pre2[i + 2] ^ x] >= l[i + 2] - 1) return true;
}
if (i + 1 <= n && vis[i + 1] && ((a[i] & x) == x)) {
rep(v, i + 2, r[i + 1]) {
if (l[i + 1] - 1 <= i && tag[pre2[v] ^ x] == tim && las[pre2[v] ^ x] >= l[i + 1] - 1) return true;
}
}
}
return false;
};
ll ans = 0;
frep(i, 17, 0) {
if (check(ans | (1LL << i))) ans = (ans | (1LL << i));
}
cout << ans << endl;
return;
}
|
D
题目大意:给定一个排列 $p$ ,对于每个下标 $i$ ,你可以跳到 $j$ ,当且仅当 $j \lt i$ 或者 $p_j$ 是第一个大于 $p_i$ 的位置,定义 $f(i,j)$ 为从 $i$ 到 $j$ 的最小跳跃数,求 $\sum\limits_{i \not ={j}} f(i,j)$ 。
数据范围: $1 \leq \sum n \leq 10^6$
思路:本题赛后补题时没想出来,参考了新加坡国立大学maomao90同学的做法。
首先很显然的是,当 $i\gt j$ 时 $f(i,j)=1$ ,因此只需考虑 $i\lt j$ 时如何求解。
由于题目很显著的单调栈结构,我们可以建一棵单调栈树,从而通过在树上操作求解,更严谨地说,应该是一个单调栈森林,如果 $i \lt j$ 且它们分属不同的树,那么它们不互相可达。
观察一下树的性质,不难发现,每棵树的根节点是原数组中的后缀最大值,以及每棵子树都对应了原数组中的一段连续区间,且一个节点的儿子从左到右在原数组中的下标逐步增大。
现在来考虑一下,如果当前 $i$ 位于非第一个儿子子树内,如果它不是根节点的亲儿子,那么它完全可以跳到第一个儿子处,然后直接跳到根节点,再跳到任意节点,这里只有三步,如果它是亲儿子,那么直接跳到根节点,再跳到任意节点即可。
如果当前 $i$ 位于第一个儿子,那么必须先一步一步跳到第一个儿子处,然后跳到根节点,再跳到任意顶点,但是如果它不是位于最左边的那条链,那么它会借助上面所说的捷径,而捷径在更深层的树形DP中已经被统计过了。
因此,实现层面上,我们可以维护距离为 $0,1,2$ 的节点数量,以及距离大于等于 $3$ 的总距离,然后树形DP统计即可,由于此处 $n$ 是 $10^6$ ,所以使用 array<ll,4> 会爆栈,只能用结构体初始化去卡内存。
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
| struct Node {
int a[3];
ll b;
};
void solve() {
ll n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i], a[i]--;
ll ans = (n - 1) * n / 2;
stack<int> s;
vi r(n, n);
frep(i, n - 1, 0) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (!s.empty()) r[i] = s.top();
s.push(i);
}
vvi ma(n);
rep(i, 0, n - 1) {
if (r[i] != n) ma[r[i]].push_back(i);
}
vi siz(n);
auto dfs = [&](this auto&& dfs, int x, int pa) -> void {
siz[x] = 1;
for (auto& p : ma[x]) {
if (p == pa) continue;
dfs(p, x);
siz[x] += siz[p];
}
return;
};
rep(i, 0, n - 1) {
if (r[i] == n) dfs(i, -1);
}
auto dfs2 = [&](this auto&& dfs2, int x, bool flag) -> Node {
Node res = {{1, 0, 0}, 0};
if (ma[x].empty()) return res;
ll idx = ma[x][0];
ll re = siz[x] - siz[idx] - 1;
auto tem = dfs2(idx, flag);
Node cur = {0, tem.a[0], tem.a[1], tem.b + siz[idx] - tem.a[0] - tem.a[1] - tem.a[2] + 3 * tem.a[2]};
ans += (flag ? cur.a[1] + 2 * cur.a[2] + cur.b : cur.a[1] + 2 * cur.a[2] + 3 * (siz[idx] - cur.a[0] - cur.a[1] - cur.a[2]));
Node cur2 = {0, cur.a[0], cur.a[1], cur.b + siz[idx] - cur.a[0] - cur.a[1] - cur.a[2] + 3 * cur.a[2]};
ans += (flag ? cur2.a[1] + 2 * cur2.a[2] + cur2.b : cur2.a[1] + 2 * cur2.a[2] + 3 * (siz[idx] - cur2.a[0] - cur2.a[1] - cur2.a[2])) * re;
rep(i, 0, 2) res.a[i] += cur.a[i];
res.b += cur.b;
for (auto& p : ma[x]) {
if (p == idx) continue;
dfs2(p, false);
re -= siz[p];
ans += 1 + 2 * (siz[p] - 1);
ans += (2 + 3 * (siz[p] - 1)) * re;
res.a[1]++, res.a[2] += siz[p] - 1;
}
return res;
};
rep(i, 0, n - 1) {
if (r[i] == n) dfs2(i, true);
}
cout << ans << endl;
return;
}
|
E
题目大意:给定数组 $a_1,\ldots,a_n$ ,考虑所有中序遍历结果为它的树,定义一条边的贡献为,删除它后两个连通块各自的异或和为 $X$ 和 $Y$ ,则这条边的贡献为 $X+Y$ ,一棵树的贡献定义为其所有边的贡献之和,请求出所有可能树的总贡献,并模 $998244353$ 。
数据范围: $1 \leq \sum n \leq 2 \cdot 10^5, 0 \leq a_i \lt 2^{18}$
思路:本题赛时看都没看,赛后听说很简单歪榜了,于是补题时推了半小时推出了式子并红温。
先把式子列出来, $tot=\sum\limits_{Tree}\sum\limits_{Edge}(X+Y)$ ,然后很显然地需要考虑交换求和顺序,也就是 $\sum\limits_{Edge}\sum\limits_{Tree}(X+Y)$ 。
而由于中序遍历的性质,可以知道,对于一条边,它的子树一定是 $[l,r]$ 的形式,因此原式化为 $\sum\limits_{l \not ={r}}\sum\limits_{Tree}((pre_{r} \oplus pre_{l-1})+(tot2 \oplus (pre_{r} \oplus pre_{l-1})))$ ,这里 $tot2=a_1 \oplus a_2 \ldots a_{n}$ 。
然后,就分为两部分了,一部分是快速计算当前 $l \not ={r}$ 的情况有多少种树的形态,另一个是考虑如何快速计算后面这部分。
先看树的形态,由于一个非常熟悉的结论,也就是中序遍历固定,大小为 $n$ 的树有 $C_n$ 棵(这里 $C_n$ 是卡特兰数),这样子树的方案数就定下来了,接着打表,发现对于 $l \not ={r}$ ,一共有 $C_mC_{n-m},m=r-l+1$ 种。
于是我们发现,实际的树形态数只跟 $r-l+1$ 有关,那么完全可以考虑对于 $r-l+1=i$ 的情况下如何求值(前面的树形态系数可以用NTT求出),发现当 $tot2$ 在某一位上为 $1$ 时,那么无论 $pre_{r} \oplus pre_{l-1}$ 的值如何,这位都贡献 $1$ ,反之贡献 $2pre_{r} \oplus pre_{l-1}$ (拆位贡献),也就是考虑如何快速求出 $\sum\limits_{j=1}^{n-i+1}pre_{j-1} \oplus pre_{j+i-1}$ ,然后这也可以看成模 $2$ 加法下的NTT(把另一个 $pre$ 反转一下),于是就做完了。
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
| // NTT求卷积,模数998244353,原根3
// convolution(a, b)返回c,其中c[k]=sum(a[i]*b[j]),i+j=k
constexpr ll MOD = 998244353;
constexpr ll G = 3;
ll qpow(ll x, ll y) {
ll res = 1;
while (y) {
if (y & 1) res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
void ntt(vl& a, bool inv) {
int n = sz(a);
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
ll wlen = qpow(G, (MOD - 1) / len);
if (inv) wlen = qpow(wlen, MOD - 2);
for (int i = 0; i < n; i += len) {
ll w = 1;
rep(j, 0, len / 2 - 1) {
ll u = a[i + j];
ll v = a[i + j + len / 2] * w % MOD;
a[i + j] = u + v < MOD ? u + v : u + v - MOD;
a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + MOD;
w = w * wlen % MOD;
}
}
}
if (inv) {
ll inv_n = qpow(n, MOD - 2);
for (ll& x : a) x = x * inv_n % MOD;
}
}
vl convolution(vl a, vl b) {
if (a.empty() || b.empty()) return {};
int need = sz(a) + sz(b) - 1;
int n = 1;
while (n < need) n <<= 1;
a.resize(n);
b.resize(n);
ntt(a, false);
ntt(b, false);
for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
ntt(a, true);
a.resize(need);
return a;
}
vl polymul(vl& a, vl& b, int lim) {
vl c = convolution(a, b);
if (sz(c) > lim) c.resize(lim);
return c;
}
vl polypow(vl a, int y, int lim) {
vl res(1, 1);
while (y > 0) {
if (y & 1) res = polymul(res, a, lim);
y >>= 1;
if (y) a = polymul(a, a, lim);
}
return res;
}
/*
使用示例:
void solve() {
int n, m;
cin >> n >> m;
vl a(n + 1), b(m + 1);
rep(i, 0, n) cin >> a[i];
rep(i, 0, m) cin >> b[i];
vl c = convolution(a, b);
rep(i, 0, n + m) cout << c[i] << " \n"[i == n + m];
}
输入:
2 1
1 2 3
4 5
输出:
4 13 22 15
*/
constexpr int MX = 4e5 + 5;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, int n) {
ll res = 1;
for (; n; n >>= 1) {
if (n % 2) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD; // 预处理阶乘
INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
} // 预处理逆元
return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl pre(n + 1);
rep(i, 1, n) pre[i] = pre[i - 1] ^ a[i - 1];
ll tot = pre[n];
vl c(n + 1);
rep(i, 0, n) c[i] = mul(F[2 * i], mul(INV_F[i], INV_F[i + 1]));
vl d(n + 1);
rep(i, 1, n - 1) d[i] = mul(c[i], c[n - i]);
ll ans = 0;
ll tot2 = 0;
rep(i, 1, n - 1) tot2 = (tot2 + mul(d[i], n + 1 - i)) % MOD;
rep(i, 0, 17) {
if ((tot >> i) & 1) {
ans = (ans + mul(qpow(2, i), tot2)) % MOD;
continue;
}
vl x(n + 1);
rep(j, 0, n) x[j] = ((pre[j] >> i & 1) ? MOD - 1 : 1);
auto y = x;
ranges::reverse(y);
vl cv = convolution(x, y);
ll tem = tot2;
rep(j, 1, n - 1) tem = (tem - mul(d[j], cv[n - j]) + MOD) % MOD;
ans = (ans + mul(qpow(2, i), tem)) % MOD;
}
cout << ans << endl;
return;
}
|