正式训练
E. Find Maximum
由于 $f$ 的表达式中屡次出现 $\bmod 3$，我们直接考虑将 $x$ 理解为三进制整数。这时候我们会发现使 $f$ 值加一的操作其实有两种，一种是在 $x$ 后面加一个 $0$，一种是在不进位的前提下给 $x$ 的最低为加一。
这就不难得出结论：$f(x)$ 是 $x$ 在三进制表示下的数码和 + 位数。
题目中又要求我们在 $x \in [l, r]$ 的限制下最大化 $f(x)$，我们自然希望求得的 $x$ 含有尽可能长的全 $2$ 后缀。但为了满足 $x \leq r$ 的限制，在这个后缀的前一位应当比 $x$ 小 $1$，再往前的位应该和 $r$ 相等。很凑巧的是这一构造十分契合 $x \geq l$ 的约束条件，因此直接枚举相等的前缀长度即可。
时间复杂度 $O(\log 10^{18})$。
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
int solve() {
LL x, y;
cin >> x >> y;
vector<int> a, b;
while(x) {
a.push_back(x % 3);
x /= 3;
}
while(y) {
b.push_back(y % 3);
y /= 3;
}
while(a.size() < b.size()) {
a.push_back(0);
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int pref = 0;
size_t i = 0;
while(i < b.size() && a[i] == b[i]) {
pref += b[i] + 1;
i++;
}
int ans = 0;
while(i < b.size()) {
if(i == 0 && b[i] == 1) {
ans = max<int>(ans, pref + 3 * (b.size() - i - 1));
} else {
ans = max<int>(ans, pref + b[i] + 3 * (b.size() - i - 1));
}
pref += b[i] + 1;
i++;
}
return max(pref, ans);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
cout << solve() << "\n";
}
return 0;
}
|
L. Tree
为简便起见，记满足题目中两条性质的集合分别为 A 类集和 B 类集。显然 A 类集必然为树上某一条链的子集。
事实上不难发现任给一棵树，如果只用 B 类集对其划分，那么集合的个数一定等于深度（将深度相同的点放在一个集合里即可），而深度又对应了树上的最长链（即最大的 A 类集）。
我们可以每次从树上抽走一条最长的链（即使在 A 类集个数 +1 的情况下尽可能多地减少 B 类集的数量），统计整个过程中的最小集合数，直接输出即可。
时间复杂度可以做到 $O(n)$，训练时我图省事用 std::set 动态维护最小值，复杂度挂了个 $\log$。
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
| #include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
vector<int> G[MX];
int dep[MX], son[MX];
bool vis[MX];
void dfs(int u) {
int cur = 0, ss = -1;
for(int v : G[u]) {
dfs(v);
if(dep[v] > cur) {
cur = dep[v];
ss = v;
}
}
dep[u] = cur + 1;
son[u] = ss;
}
int solve() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
G[i].clear();
}
memset(vis + 1, false, sizeof(bool[n]));
for(int i = 2; i <= n; i++) {
int fa;
cin >> fa;
G[fa].push_back(i);
}
dfs(1);
set<pair<int, int>, greater<pair<int, int>>> nodes;
for(int i = 1; i <= n; i++) {
nodes.emplace(dep[i], i);
}
int ans = dep[1], cnt = 0;
while(!nodes.empty()) {
int u = nodes.begin() -> second;
while(u != -1) {
nodes.erase(make_pair(dep[u], u));
u = son[u];
}
cnt++;
ans = min(ans, cnt + nodes.begin()->first);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
cout << solve() << "\n";
}
return 0;
}
|
B. Cells Coloring
假设我们已经知道了颜色数 $k$ 的取值，那么最小的未染色格子数量 $z$ 可以由最大流直接求出。
同时我们知道最大流是凸的，即 $z$ 对 $k$ 的二阶导数非负（有点类似于边际效用递减，证明很显然），由此可知 $ck + dz$ 的二阶导同样非负，那么对这个函数的最小化问题就可以用三分法求解。
时间复杂度大概是 $O(n^3 \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
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
152
| #include <bits/stdc++.h>
using namespace std;
template<typename flow_t = int>
struct MaxFlow_ISAP {
const flow_t MAX_VAL = numeric_limits<flow_t>::max();
struct edge_t {
int to, rev;
flow_t f;
edge_t() {}
edge_t(int _t, int _r, flow_t _f) : to(_t), rev(_r), f(_f) {}
};
vector<vector<edge_t>> G;
vector<typename vector<edge_t>::iterator> cur;
int V;
vector<int> gap, dep;
MaxFlow_ISAP(int v) : G(v + 1), cur(v + 1), V(v) {}
void add_edge(int u, int v, flow_t f) {
G[u].emplace_back(v, G[v].size(), f);
G[v].emplace_back(u, G[u].size() - 1, 0);
}
void BFS(int T) {
gap.assign(V + 2, 0);
dep.assign(V + 1, 0);
queue<int> Q;
Q.push(T), ++gap[dep[T] = 1];
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(edge_t &e : G[u]) {
int v = e.to;
if(dep[v]) continue;
Q.push(v), ++gap[dep[v] = dep[u] + 1];
}
}
}
flow_t dfs(int u, flow_t flow, const int S, const int T) {
if(u == T || !flow) return flow;
flow_t w, used = 0;
for(auto &i = cur[u]; i != G[u].end(); i++) {
if(i -> f && dep[i -> to] == dep[u] - 1) {
w = dfs(i -> to, min(flow - used, i -> f), S, T);
i -> f -= w, G[i -> to][i -> rev].f += w;
used += w;
}
if(used == flow) return flow;
}
if(!--gap[dep[u]]) dep[S] = V + 1;
if(dep[u] <= V) ++dep[u];
++gap[dep[u]], cur[u] = G[u].begin();
return used;
}
flow_t operator() (int S, int T) {
flow_t ans = 0;
BFS(T);
while(dep[S] <= V) {
for(int i = 1; i <= V; i++) cur[i] = G[i].begin();
ans += dfs(S, MAX_VAL, S, T);
}
return ans;
}
};
using LL = long long;
LL solve() {
int n, m, c, d;
cin >> n >> m >> c >> d;
if(c == 0 || d == 0) {
return 0;
}
vector<pair<int, int>> edges;
vector<int> cntr(n), cntc(m);
for(int i = 0; i < n; i++) {
string qwq;
cin >> qwq;
for(int j = 0; j < m; j++) {
if(qwq[j] == '.') {
edges.emplace_back(i + 1, j + 1);
cntr[i]++;
cntc[j]++;
}
}
}
int L = 0, R = 0;
R = max(R, *max_element(cntr.begin(), cntr.end()));
R = max(R, *max_element(cntc.begin(), cntc.end()));
vector<LL> cache;
cache.assign(R + 2, -1);
auto get_ans = [&] (int x) {
if(cache[x] != -1) {
return cache[x];
}
int S = n + m + 1, T = S + 1;
MaxFlow_ISAP sol(n + m + 2);
for(auto [l, r] : edges) {
sol.add_edge(l, n + r, 1);
}
for(int i = 1; i <= n; i++) {
sol.add_edge(S, i, x);
}
for(int i = 1; i <= m; i++) {
sol.add_edge(n + i, T, x);
}
LL ans = sol(S, T);
return cache[x] = (LL)c * x + d * (edges.size() - ans);
};
while(L <= R) {
int mid = (L + R) / 2;
LL cur_l = get_ans(mid);
LL cur_r = get_ans(mid + 1);
if(cur_l > cur_r) {
L = mid + 1;
} else {
R = mid - 1;
}
}
LL ans = numeric_limits<LL>::max();
for(LL val : cache) {
if(val != -1) {
ans = min(ans, val);
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << solve() << "\n";
return 0;
}
|
A. Bridge
不难发现当一座桥架起来后桥之后的两道路永远不可能在上桥的那一侧被走到了。于是我们只需要维护 $n$ 条相互独立的链，而搭桥操作就是将这对应两条链的两个后缀交换。
可以用 $n$ 个独立的平衡树做到这件事情，即 LCT 所维护的链之间的连接信息是多余的。
为了实现方便可以提前离线下所有的询问来确定所有链上的标记点有哪些。时间复杂度 $O((n + q) \log n)$。
这题我只参与思路构筑，没有上手写，因此不贴代码。
训练开局我照常从头开始读题，发现 ABC 都很微妙地处于一种可做但不完全可做的状态。
这时候两个队友分别签完了 J 和 F，然后一个队友说要上机打 E 的表，并且给我简述了题意。我一听直接会做了，于是抢占了原计划用于打表的机时直接开始写 E，并让队友做一下 C。E 题代码本来没什么细节，但由于我好久没写这种类似数位 DP 的题导致手生了，足足写了 18min 才过。
在这 18min 里两位队友口胡出了 C 和 G 的做法，E 过了之后不到 5min 队友直接过了 C，然后换另一个队友上去写 G，我们两个没机时的一合计又在 G 过之前想出了 L 的做法。过了 G 之后我直接上机写 L，同样因为手生足足写了 19min。
这时是 81min。
此后 1h 我又想出了 B，两位队友则在搞 A。最终由于题意传达过程中出现了信息失真导致绕了很多弯路，270min 的时候才过 A。
最终本场训练以 0 dirt 8AC 的优秀成绩喜提 VP Au（）今年没选西安站感觉血亏（
其实过了 B 之后我们一直是 A 和 D 同时在想。不过 D 题我们几个都跑偏到最短路上去了死活压不下来复杂度，又发现 A 题意理解假了抓紧去修锅，只得作罢。赛后看了题解，一看见“倍增”俩字，我和一个队友直接会了……
赛后补题
D. Contests
本来想的是答案不会比维数超过太多，但样例直接给了一组答案为 $n - 1$ 的，这个想法直接报废。
我们可以每一步都会走到某一场比赛上可到达的最靠前的位次，然后等跳到足够靠前了最后一步再直接在当前比赛中走到 $y$。可以记 $f_{i, j, k}$ 表示 $j$ 这个人跳 $2^i$ 步最多能到比赛 $k$ 的第几名。这玩意的预处理可以用倍增法在 $O(nm^2 \log n)$ 时间内求出。
考虑查询。类似倍增法 LCA 的查询，我们需要求出「在任何一场比赛中都跳不到 $y$ 及以前任意点的最大步数」。最后输出答案的时候需要 +2，分别对应跳到 y 之前的一步（最后一跳）以及在最后一跳落脚的比赛中跳到 $y$（最后一步）。单次查询的时间是 $O(m^2 \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
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
| #include <bits/stdc++.h>
using namespace std;
const int MX = 100005;
const int MXLG = 17;
const int INF = 0x3F3F3F3F;
int rnklist[5][MX], rnk[5][MX];
int dp[MXLG + 1][MX][5];
void update(int &a, int b) {
if(a == 0 || a > b) a = b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++) {
for(int j = 1; j <= n; j++) {
int val;
cin >> val;
rnklist[i][j] = val;
rnk[i][val] = j;
}
}
for(int i = 0; i < m; i++) {
vector<bool> vised(n + 1);
vector<int> iter(m, 1);
for(int j = 1; j <= n; j++) {
int cur = rnklist[i][j];
for(int k = 0; k < m; k++) {
update(dp[0][cur][k], iter[k]);
}
vised[cur] = true;
for(int k = 0; k < m; k++) {
while(iter[k] <= n && vised[rnklist[k][iter[k]]]) iter[k]++;
}
}
}
for(int i = 1; i <= MXLG; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 0; k < m; k++) {
int &cur = dp[i][j][k];
cur = dp[i - 1][j][k];
for(int l = 0; l < m; l++) {
int tmp = dp[i - 1][j][l];
if(tmp == n + 1) {
assert(false);
}
tmp = rnklist[l][tmp];
cur = min(cur, dp[i - 1][tmp][k]);
}
}
}
}
function<int(int, int)> solve = [&] (int x, int y) {
vector<int> point(m);
for(int i = 0; i < m; i++) {
if(rnk[i][x] < rnk[i][y]) {
return 1;
}
point[i] = x;
}
int ans = 0;
for(int i = MXLG; i >= 0; i--) {
vector<int> tmp = point;
for(int cur : point) {
for(int j = 0; j < m; j++) {
int rk = dp[i][cur][j];
if(rk < rnk[j][tmp[j]]) {
tmp[j] = rnklist[j][rk];
}
}
}
bool flag = false;
for(int j = 0; j < m; j++) {
if(rnk[j][tmp[j]] <= rnk[j][y]) {
flag = true;
break;
}
}
if(!flag) {
ans += 1 << i;
point = tmp;
}
}
return ans <= n ? ans + 2 : -1;
};
int q;
cin >> q;
while(q--) {
int x, y;
cin >> x >> y;
cout << solve(x, y) << "\n";
}
return 0;
}
|
H. Power of Two
中心思想是先用大部分操作凑一个 $0$ 出来，然后用剩下的 or 和 xor 把尽可能多的位置 1。这里面有一车细节，赛场上谁写谁 tm 是五星秘术师（
下面简单说说分类讨论的过程。为了方便描述，记 $d$ 表示给出的互不相同的 $c_i$ 的个数，而“奇数”和“偶数”分别指给出次数（而非 $c_i$ 本身）为奇数和偶数的 $c_i$。
两种平凡情形
- 当 $y + z \leq d$，即 or 和 xor 的个数之和不多于 $d$ 时：
显然我们需要用这些 or 和 xor 在最后把较高的那些位置成 $1$，在此之前消耗掉全部的 and 即可。 - 当 $y \geq d$，即 or 的个数不少于 $d$ 时：
不论我们前期怎么乱用 and 和 xor，最后总有足够多的 or 把所有位置 $1$。
在后面的讨论中，我们总是假定 $y + z > d$ 以及 $y < d$。注意 $y + z > d$ 蕴含了至少存在一个 $c_i$ 出现了不止一次。
只有两种运算的退化情形
不难发现 $z = 0$ 时一定会落入前述两种平凡情形之一，故这里并不需要专门讨论 $z = 0$。
若 $x = 0$，即没有 and 操作
在非平凡的情形下一定有 $y < d$，我们尝试将 or 分配给不同的 $c_i$。
注意到 or 会无条件置 $1$，而 xor 只有在奇数次的时候才会置 $1$，因此一个很自然的想法是把 or 尽可能分给出现次数为偶数的数。
如果分配完偶数后 or 有剩余，那么可以把 or 当作 xor 分配给奇数；如果 or 不够给所有偶数，那么一定会有偶数因为分配到的操作全是 xor 使得对应位被置 $0$，我们自然希望分配到 or 的是最大的那些 $c_i$。
若 $y = 0$，即没有 or 操作
在非平凡情况下一定有 $z > d$，因此我们可以先取出 $d$ 个 xor 用于最后将所有位置 $1$。下面我们只考虑用 and 和剩下的 xor 凑出尽可能小的数。
最简单的情形是有至少 $2$ 个 $c_i$ 的出现次数大于 $1$（不妨设为 $c_1$ 和 $c_2$）且 and 操作至少有两个，此时我们有
$$
A \operatorname{and} 2^{c_1} \operatorname{and} 2^{c_2} = 0
$$
其中 $A$ 是其他数和运算符任意计算得到的结果。
如果只有一个数出现多于一次，那么余下部分的结果仅与 xor 操作次数的奇偶性有关。当该结果非零时可以通过调整使得被置 $1$ 的位在最小的 $c_i$ 处。
如果 and 操作只有一个，那么余下的结果应该依赖于 $> 1$ 部分的异或和。若异或和的 $c_i$ 位不为 $0$，则可以通过将 $2^{c_i}$ 和剩下的异或和 and 起来凑出一个 $0$。否则，无论怎么用这个 and 都无法得到 $0$，这时我们退而求其次将出现多余 $1$ 次的最小的 $c_i$ 置 $1$。
其他情形
正如前面所分析的，因为 $y < d$，我们希望把 or 分配给不同的 $c_i$，且这些 $c_i$ 最好是偶数。这时就会出现两种情况：or 操作有剩余或偶数有剩余。
当然，我们的大思路仍然是先用剩余操作尽量凑出 $0$，再用上述 or 和 xor 将所有位置 $1$。
or 操作有剩余
这就意味着必然有必然有一部分奇数被分配到一个 or。
令 $E$ 表示偶数集合，$O_o$ 和 $O_x$ 分别表示被分配到 or 的奇数集合和其他奇数集合。
显然 $E$ 和 $O_o$ 中 $> 1$ 的部分可以随意填 xor，但 $O_x$ 中每个数必须被分配到偶数个 xor（不含预留的那个）。
我们可以尽量先用 $E$ 和 $O_o$ 消耗 xor。如果 xor 还有剩余，易知 $O_x$ 消耗的 xor 数量一定是偶数，因此当不满足这一条件的时候需要从 $E$ 或 $O_o$ 中还回来一个 xor（$|E| + |O_o| = y > 0$ 保证了一定有的还）。
这之后的所有空位全填 and 即可。易知这样凑出来的结果恰好达到理论上界（即所有位置 $1$）。
偶数有剩余
这就意味着必然有必然有一部分偶数被分配到一个 xor。
令 $E_o$ 和 $E_x$ 分别表示被分配到 or 和 xor 的偶数集合，$O$ 为奇数集合。类似地，$E_o$ 中 $> 1$ 的部分可以随意填 xor，但 $E_x$ 和 $O$ 中必须配对填。
我们尝试优先消耗 $O$ 以及 $E_x$ 贡献的 xor 位，如果还有剩余则消耗 $E_o$ 位。
这样三轮消耗之后，剩余的空位有且仅有 $E_x$ 中的每数一个。无论此时 xor 位是否有剩余，由于还剩下至少一个 and 没有用，随便怎么填结果都是最大值。
下面是本题的完整代码。
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
| #include <bits/stdc++.h>
using namespace std;
const int MX = 65536;
void solve() {
int n, x, y, z;
cin >> n >> x >> y >> z;
map<int, int> cnt;
for(int i = 1; i <= n; i++) {
int val;
cin >> val;
cnt[val]++;
}
// statistics
vector<int> odds, evens, gt1;
for(auto [key, value] : cnt) {
((value & 1) ? odds : evens).push_back(key);
if(value > 1) {
gt1.push_back(key);
}
}
string ans(n, '0'), op_array;
vector<int> op_num;
function<void(char, int)> update_answer = [&] (char c, int val) {
op_array.push_back(c);
op_num.push_back(val);
};
function<int()> pop_answer = [&] {
int ret = op_num.back();
op_array.pop_back();
op_num.pop_back();
return ret;
};
if(y + z <= cnt.size()) { // or + xor <= #
for(auto &[key, val] : cnt) {
while(x > 0 && val > 1) {
update_answer('&', key);
val--, x--;
}
}
for(auto &[key, val] : cnt) {
if(x > 0) {
update_answer('&', key);
x--;
} else if(y > 0) {
update_answer('|', key);
ans[key] = '1';
y--;
} else {
update_answer('^', key);
ans[key] = '1';
z--;
}
}
} else if(y >= cnt.size()) { // or >= #
for(auto &[key, val] : cnt) {
while(x > 0 && val > 1) {
update_answer('&', key);
val--, x--;
}
while(z > 0 && val > 1) {
update_answer('^', key);
val--, z--;
}
}
assert(x == 0 && z == 0);
for(auto &[key, val] : cnt) {
while(val--) {
update_answer('|', key);
ans[key] = '1';
}
}
} else if(x == 0) { // only or + xor
while(y > 0 && !evens.empty()) {
int key = evens.back(), &value = cnt[key];
while(value > 1) {
update_answer('^', key);
value--;
}
update_answer('|', key);
y--, value--;
ans[key] = '1';
evens.pop_back();
}
for(int i = 0; i < y; i++) {
update_answer('|', odds[i]);
ans[odds[i]] = '1';
cnt[odds[i]]--;
}
for(auto [key, value] : cnt) {
while(value--) {
update_answer('^', key);
ans[key] ^= 1;
}
}
} else if(y == 0) { // only and + xor
z -= cnt.size();
if(gt1.size() == 1) {
if(z % 2 == 1) {
update_answer('&', cnt.begin()->first);
cnt.begin()->second--;
x--;
}
int special = gt1.front();
while(x > 0) {
update_answer('&', special);
x--, cnt[special]--;
}
for(auto &[key, value] : cnt) {
while(value--) {
update_answer('^', key);
ans[key] ^= 1;
}
}
} else if(x == 1) {
bool flag = false;
int special = gt1.front();
for(int key : gt1) {
if(cnt[key] % 2 == 0) {
special = key;
flag = true;
break;
}
}
if(flag) { // xor sum != 0
cnt[special]--;
for(int key : gt1) {
int &value = cnt[key];
while(value > 1) {
update_answer('^', key);
value--;
}
}
update_answer('&', special);
for(auto [key, _] : cnt) {
update_answer('^', key);
ans[key] = '1';
}
} else {
update_answer('&', cnt.begin()->first);
cnt.begin()->second--;
for(auto [key, value] : cnt) {
while(value--) {
update_answer('^', key);
ans[key] ^= 1;
}
}
}
} else {
cnt[gt1.front()]--;
cnt[gt1.back()]--;
x -= 2;
for(int key : gt1) {
int &value = cnt[key];
while(value > 1) {
if(z > 0) {
update_answer('^', key);
z--;
} else {
update_answer('&', key);
x--;
}
value--;
}
}
update_answer('&', gt1.front());
update_answer('&', gt1.back());
for(auto [key, _] : cnt) {
update_answer('^', key);
ans[key] = '1';
}
}
} else { // or + xor > # && or < #
z -= cnt.size() - y;
if(y >= evens.size()) { // or >= #evens
sort(odds.begin(), odds.end(), [&] (int u, int v) {
return cnt[u] > cnt[v];
});
for(int key : evens) {
int &value = cnt[key];
while(z > 0 && value > 1) {
update_answer('^', key);
z--, value--;
}
}
y -= evens.size();
for(int i = 0; i < y; i++) {
int key = odds[i], &value = cnt[key];
while(z > 0 && value > 1) {
update_answer('^', key);
z--, value--;
}
}
if(z != 0) { // xor left
if(z % 2 == 1) {
z++, cnt[pop_answer()]++;
}
for(int i = y; i < odds.size(); i++) {
int key = odds[i], &value = cnt[key];
while(value > 1 && z > 0) {
update_answer('^', key);
value--, z--;
}
}
}
assert(z == 0);
for(auto &[key, value] : cnt) {
while(x > 0 && value > 1) {
update_answer('&', key);
x--, value--;
}
}
assert(x == 0);
for(int key : evens) {
update_answer('|', key);
ans[key] = '1';
}
for(int i = 0; i < odds.size(); i++) {
update_answer(i < y ? '|' : '^', odds[i]);
ans[odds[i]] = '1';
}
} else { // not too bad
sort(evens.begin(), evens.end(), [&] (int u, int v) {
return cnt[u] < cnt[v];
});
if(z % 2 == 1) {
int key = evens.back();
update_answer('^', key);
cnt[key]--;
z--;
}
for(int key : odds) {
int &value = cnt[key];
while(z > 0 && value > 1) {
update_answer('^', key);
z--, value--;
}
}
y = evens.size() - y;
for(int i = 0; i < evens.size(); i++) {
int key = evens[i], &value = cnt[key];
while(z > 0 && value > 1 + (i < y)) {
update_answer('^', key);
z--, value--;
}
}
for(int i = 0; i < y; i++) {
int key = evens[i], &value = cnt[key];
while(z > 0 && value > 1) {
assert(value == 2);
update_answer('^', key);
z--, value--;
}
}
for(auto &[key, value] : cnt) {
while(x > 0 && value > 1) {
update_answer('&', key);
value--, x--;
}
}
assert(x == 0);
for(int key : odds) {
update_answer('^', key);
ans[key] = '1';
}
for(int i = 0; i < evens.size(); i++) {
update_answer(i < y ? '^' : '|', evens[i]);
ans[evens[i]] = '1';
}
}
}
reverse(ans.begin(), ans.end());
cout << ans << "\n" << op_array << "\n";
for(int val : op_num) {
cout << val << ' ';
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}
|
I. Square Grid
首先考虑一维情形，即在数轴上用 $t$ 步从 $x_0$ 走到 $x_1$ 但全程不离开闭区间 $[1, n]$ 的方案数。这个问题太典了，典到我一直以为我的错误做法有理有据。
如果只有一个方向（如左侧）有限制，我们可以按照类似 Catalan 数通项公式的某个几何证明那样在「打破限制的走法」与「由 $-x_0$ 无限制地走到 $x_1$ 的走法」之间建立一一对应。
现在两个方向全部有限制，一个自然的想法是把 $x_0$ 往两边分别对称到 $-x_0$ 和 $2(n + 1) - x_0$，然后减去这部分的方案。直觉告诉我们一定多减去了两次走出端点的走法，需要把这部分加回来。
我们发现「先穿过左端点，再穿过右端点」等价于将起点移动到 $2(n + 1) + x_0$，而「先穿过右端点，再穿过左端点」等价于将起点移动到 $-2(n + 1) + x_0$。
在这一步中，我们求的是有过「先穿过左端点，再穿过右端点」的方案数，但并没有办法保证在此之前或之后没有再穿过端点。
如此归纳地进行下去，注意到穿过端点是一定是左右交替进行的，不难得出：所有穿过奇数次端点的走法起点为 $-x_0 + kN$，穿过偶数次端点的走法起点为 $x_0 + kN$。其中 $N = 2(n + 1)$，$k$ 是任意整数。于是最终结果就是
$$
\sum_{k \in \mathbb{Z}} f(x_0 + kN, x_1) - \sum_{k \in \mathbb{Z}} f(-x_0 + kN, x_1)
$$
其中 $f(x, y)$ 表示用 $t$ 步无限制地从 $x$ 走到 $y$ 的方案数，易知 $f(x, y) = \dbinom{t}{(t + y - x) / 2}$。
不难看出上式两项都是多项式 $(1 + x)^t \bmod (x^{n+1} - 1)$ 的某项系数。
下面回到原问题。现在两个维度上都是这个问题。如果直接做的话需要考虑横向和竖向分别走了几步，最后就会凭空多一个卷积出来。
考虑将坐标系旋转 $45 \degree$（即坐标变换 $(x, y) \mapsto (x + y, x - y)$），可以发现每一步坐标的增量变成了 $(\pm 1, \pm 1)$，这样就相当于两个独立的维度同时进行，直接两个方向上分别求 $f$ 乘起来即可。
考虑统计答案。受到前面的启发，我们枚举（原坐标系）两个维度上分别穿过边界次数的奇偶性。不妨设均为奇数次，则起点的位置应该是 $(-x_0 + k_1N, -y_0 + k_2N)$，经过坐标变换后的坐标是
$$
(-(x_0 + y_0) + (k_1 + k_2)N, -(x_0 - y_0) + (k_1 - k_2)N)
$$
注意到两个维度上 $N$ 的系数 $k_1 + k_2$ 和 $k_1 - k_2$ 奇偶性是一致的，结合 $f$ 的形式，我们所求的答案就是 $(1 + x)^t \bmod (x^N - 1)$ 的某两对（距离为 $n + 1$ 的）系数的乘积之和。
时间复杂度 $O(n \log n \log t + q)$。
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
| #include <bits/stdc++.h>
using namespace std;
namespace Polynomial_NTT {
using int_t = int;
using long_t = long long;
// make sure 2*P will not cause signed overflow
constexpr int_t g = 3, P = 998244353;
constexpr int_t MXLEN = 1 << 19;
constexpr int_t inv2 = (P + 1) >> 1;
using array = int_t[MXLEN + 1];
inline size_t getLength(int_t val) {
val |= val >> 1; val |= val >> 2;
val |= val >> 4; val |= val >> 8;
val |= val >> 16;
return val + 1;
}
int_t Pow(long_t u, int_t v) {
long_t ans = 1;
for(; v; v >>= 1, u = u * u % P)
if(v & 1) ans = u * ans % P;
return (int_t)ans;
}
int_t getInv(int_t u) { return Pow(u, P - 2); }
void DFT(int_t *A, const size_t n, const int_t flag) {
static size_t rev[MXLEN + 1], preN;
if(preN != n) {
for(size_t i = 0; i < n; i++) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1));
}
preN = n;
}
for(size_t i = 0; i < n; i++)
if(i < rev[i]) swap(A[i], A[rev[i]]);
for(size_t i = 1, r = 1; i < n; i *= 2, r++) {
long_t wn = Pow(g, P - 1 + flag * ((P - 1) >> r));
for(size_t j = 0; j < n; j += i * 2) {
long_t w = 1;
for(size_t k = j; k < j + i; k++) {
int_t x0 = A[k], x1 = int_t(w * A[i + k] % P);
A[k] = (x0 + x1) % P;
A[i + k] = (x0 + P - x1) % P;
w = wn * w % P;
}
}
}
if(flag == -1) {
long_t tmp = getInv(n);
for(size_t i = 0; i < n; i++) A[i] = int_t(A[i] * tmp % P);
}
}
void multiply(int_t *res, const int_t *A, const size_t n, const int_t *B, const size_t m) {
static array _A, _B;
size_t X = getLength(n + m - 2);
memcpy(_A, A, sizeof(int_t[n])), memset(_A + n, 0, sizeof(int_t[X - n]));
memcpy(_B, B, sizeof(int_t[m])), memset(_B + m, 0, sizeof(int_t[X - m]));
DFT(_A, X, 1), DFT(_B, X, 1);
for(size_t i = 0; i < X; i++) res[i] = int_t((long_t)_A[i] * _B[i] % P);
DFT(res, X, -1);
}
} // namespace Polynomial_NTT
using LL = long long;
const int MX = Polynomial_NTT::MXLEN;
const int mod = Polynomial_NTT::P;
// ans = a^b mod (x^n - 1)
void Pow(int *ans, int *a, int b, int n) {
int n_ans = 1, n_a = 2;
while(b) {
if(b & 1) {
Polynomial_NTT::multiply(ans, ans, n_ans, a, n_a);
for(int i = n_ans + n_a - 2; i >= n; i--) {
ans[i - n] = (ans[i - n] + ans[i]) % mod;
ans[i] = 0;
}
n_ans = min(n_ans + n_a - 1, n);
}
Polynomial_NTT::multiply(a, a, n_a, a, n_a);
for(int i = n_a + n_a - 2; i >= n; i--) {
a[i - n] = (a[i - n] + a[i]) % mod;
a[i] = 0;
}
n_a = min(n_a + n_a - 1, n);
b >>= 1;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, t, q;
cin >> n >> t >> q;
n = 2 * (n + 2);
static int C[MX], P[MX];
C[0] = 1;
P[0] = P[1] = 1;
Pow(C, P, t, n);
function<LL(int, int)> calc = [&] (int x, int y) {
int dx = x + y, dy = x - y;
dx = ((dx + t) / 2 % n + n) % n;
dy = ((dy + t) / 2 % n + n) % n;
return (LL)C[dx] * C[dy];
};
while(q--) {
int x0, y0, x1, y1;
cin >> x0 >> y0 >> x1 >> y1;
++x0, ++y0, ++x1, ++y1;
if((x0 ^ y0 ^ x1 ^ y1 ^ t) & 1) {
cout << 0 << "\n";
continue;
}
LL ans = 0;
ans += calc(x1 - x0, y1 - y0);
ans += calc(x1 - x0, y1 - y0 + n);
ans += calc(-x1 - x0, -y1 - y0);
ans += calc(-x1 - x0, -y1 - y0 + n);
ans -= calc(-x1 - x0, y1 - y0);
ans -= calc(-x1 - x0, y1 - y0 + n);
ans -= calc(x1 - x0, -y1 - y0);
ans -= calc(x1 - x0, -y1 - y0 + n);
cout << (ans % mod + mod) % mod << "\n";
}
return 0;
}
|
剩下的 K 等有缘再补吧（
