正式训练
K. Stack Sort
每个栈里存的数字对应到原序列应该位置单调且权值连续递减。直接求出每个数字的位置之后暴力统计即可。
E. Identical Parity
不难发现相距为 $k$ 的两个数必定有相同的奇偶性。由此可以把整个序列拆分成 $n \bmod k$ 个长度为 $\left\lfloor \dfrac{n}{k} \right\rfloor + 1$ 的链和 $k - (n \bmod k)$ 个长度为 $\left\lfloor \dfrac{n}{k} \right\rfloor$ 的链，而我们要做的就是求不定方程
$$
x \cdot \left( \left\lfloor \frac{n}{k} \right\rfloor + 1 \right) + y \cdot \left\lfloor \frac{n}{k} \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor
$$
是否有解满足 $0 \leq x \leq n \bmod k$ 且 $0 \leq y \leq k - (n \bmod k)$。
容易写出这个不定方程的通解为
$$
x = \left\lfloor \frac{n}{2} \right\rfloor - r \cdot \left\lfloor \frac{n}{k} \right\rfloor \qquad
y = -\left\lfloor \frac{n}{2} \right\rfloor + r \cdot \left( \left\lfloor \frac{n}{k} \right\rfloor + 1 \right)
$$
直接判断即可。
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
| #include <bits/stdc++.h>
using namespace std;
bool solve(int n, int k) {
int A = n / 2, B = -A;
int tmp = n / k;
int r;
r = (A + tmp) / (tmp + 1);
B += r * (tmp + 1);
A -= r * tmp;
assert(B >= 0);
if(B > k - n % k || A < 0) {
return false;
}
if(A <= n % k) {
return true;
}
r = (A - n % k + tmp - 1) / tmp;
A -= r * tmp;
B += r * (tmp + 1);
if(B > k - n % k || A < 0) {
return false;
}
assert(A <= n % k);
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
if(solve(n, k)) {
puts("Yes");
} else {
puts("No");
}
}
return 0;
}
|
这场由于种种原因打得只有中杯水平。
开场半小时签完 MKE 之后两位队友琢磨出了 A 的做法，但因为细节过多用了将近一个小时才最终过掉。剩下三个半小时基本都在开 D 和 C。D 是一个很直白的大模拟，队友在写的时候我就跑去想 C。C 题其实半个小时不到就想到了正确做法，抢占机时后写到一半突然以为到自己之前的复杂度算错了，然后就对着一个不存在的问题思考了好久，直到最后都没发现自己的 hack 是假的。
队友写 D 也并不轻松。这种大模拟通常整个代码会有很多需要注意的点，而他本来也很不擅长写这种中长篇幅的模拟，最终前前后后写了两个半小时才过掉。
最后不到一小时想着破罐子破摔写一下 C 题的代码，结果差 10min 没写完。
其实说到底应该还是赛中任务分配的决策出了问题。我当时大概应该自己写一遍 D，说不定换完脑子回来 C 就想明白了，和 C 题死磕到最后落得个长考出臭棋的结果。仔细想想 ICPC 打砸的四场里有两场（21 年澳门和 21 年 EC）都在赛时出现了极为致命的决策失误。希望今年 EC 不会再有。
补题记录
C. DFS Order 2
我们发现实际上位置的差异完全由兄弟结点的先后顺序决定。我们可以在每个点挂一个形式幂级数 $P(x)$ 表示其兄弟结点给他贡献的偏移量，最后只需要求一遍树上前缀乘积就好了。
我们发现偏移实际上由子树大小和子树个数两个因素决定，因此形式变元应该有两个。用 $s_u$ 和 $c_u$ 分别表示以 $u$ 为根的子树的大小和 DFS 序个数，则结点 $u$ 对他的兄弟的贡献可以表示为
$$
c_u \left( 1 + x^{s_u} y \right)
$$
即如果 $u$ 在兄弟之前，则子树个数 $+1$，偏移量大小 $+ s_u$；否则二者变化量均为 $0$。但无论何种情况贡献的方案数都是 $c_u$，即当前子树 DFS 序的个数。
不妨设当前节点为 $u$，其兄弟节点为 $v_1, v_2, \cdots, v_k$，那么形式幂级数
$$
Q(x, y) = \prod_{i = 1}^{k} c_{v_i} \left( 1 + x^{s_{v_i}} y \right)
$$
的 $x^sy^t$ 项系数则表明当前有 $t$ 子树在 $u$ 之前，贡献了总计 $s$ 的偏移的方案数。
由于兄弟子树的不同顺序算作不同方案，而这在形式幂级数的乘法之中没有体现，故我们所要求的 $P$ 实际上应该是
$$
P(x) = \sum_{t} t! (k - t)! \cdot [y^t]Q(x, y)
$$
其中 $[y^t]Q(x, y)$ 表示 $Q(x, y)$ 视作 $\mathbb{F}_{998244353}\llbracket x \rrbracket$ 上的一元形式幂级数时 $y^t$ 项的系数。
考虑到 $Q$ 的形式，每次求的时候先求出所有儿子的乘积，枚举到对应儿子的时候再现场除掉即可。
最后树上求前缀乘积的部分由于是一元多项式复杂度显然是 $O(n^3)$。对前面求 $P$ 和 $Q$ 的部分，考虑到 $Q$ 的项数是 $O(n^2)$，但每次和 $Q$ 做乘除法的多项式都只有两项，因此单次乘法的复杂度是 $O(n^2)$，总复杂度也是 $O(n^3)$。
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
using poly_t = vector<vector<int>>;
const int MX = 505;
const int mod = 998244353;
int frac[MX];
int siz[MX], dfs_cnt[MX];
vector<int> G[MX];
vector<int> P[MX];
int Pow(int a, int b) {
int ans = 1;
for(; b; b >>= 1) {
if(b & 1) {
ans = (LL)ans * a % mod;
}
a = (LL)a * a % mod;
}
return ans;
}
void multiply(poly_t &cur, int siz) {
for(int i = MX - 2; i >= 0; i--) {
for(int j = 0; j + siz < MX; j++) {
if(cur[i][j] == 0) {
continue;
}
(cur[i + 1][j + siz] += cur[i][j]) %= mod;
}
}
}
void division(poly_t &cur, int siz) {
for(int i = 0; i + 1 < MX; i++) {
for(int j = 0; j + siz < MX; j++) {
if(cur[i][j] == 0) {
continue;
}
(cur[i + 1][j + siz] += mod - cur[i][j]) %= mod;
}
}
}
void dfs(int u, int f) {
int num_son = (int)G[u].size() - (f != -1);
siz[u] = 1;
dfs_cnt[u] = frac[num_son];
for(int v : G[u]) {
if(v == f) {
continue;
}
dfs(v, u);
siz[u] += siz[v];
dfs_cnt[u] = (LL)dfs_cnt[u] * dfs_cnt[v] % mod;
}
if(num_son == 0) {
return;
}
poly_t cur(MX, vector<int>(MX));
cur[0][0] = 1;
int prod = 1;
for(int v : G[u]) {
if(v == f) {
continue;
}
multiply(cur, siz[v]);
prod = (LL)prod * dfs_cnt[v] % mod;
}
for(int v : G[u]) {
if(v == f) {
continue;
}
division(cur, siz[v]);
for(int i = 0; i < num_son; i++) {
LL factor = (LL)frac[i] * frac[num_son - 1 - i] % mod;
for(int j = 0; j < MX; j++) {
if(cur[i][j] == 0) {
continue;
}
P[v][j] = (P[v][j] + cur[i][j] * factor) % mod;
}
}
int coef = (LL)prod * Pow(dfs_cnt[v], mod - 2) % mod;
for(int &val : P[v]) {
val = (LL)val * coef % mod;
}
multiply(cur, siz[v]);
}
}
// A = A * B * x
void mult(vector<int> &A, const vector<int> &B) {
vector<int> ans(MX);
for(int i = 0; i < MX; i++) {
for(int j = 0; i + j + 1 < MX; j++) {
(ans[i + j + 1] += (LL)A[i] * B[j] % mod) %= mod;
}
}
A = ans;
}
void dfs2(int u, int f) {
for(int v : G[u]) {
if(v == f) {
continue;
}
mult(P[v], P[u]);
dfs2(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
frac[0] = 1;
for(int i = 1; i <= n; i++) {
frac[i] = (LL)frac[i - 1] * i % mod;
}
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1; i <= n; i++) {
P[i].resize(MX);
}
P[1][0] = 1;
dfs(1, -1);
dfs2(1, -1);
for(int i = 1; i <= n; i++) {
for(int j = 0; j < n; j++) {
cout << (LL)P[i][j] * dfs_cnt[i] % mod << ' ';
}
cout << '\n';
}
return 0;
}
|
其他题目暂咕，啥时候想起来补了再更新。
