我生待明日，万事成蹉跎。
town
http://222.180.160.110:61235/contest/6407/problem/1
给定一棵大小为 \(n\) 的树，点有点权，欲将树划分为若干个连通块，使得每个块内的点权异或和都为 \(x\)，求方案数，模 \(998244353\)。
\(n\le 10^6,0\le x\le 10^9\)。
记 \(u\) 引导的子树异或和为 \(s_u\)。把连通块转化为对断边的讨论。考察一条最末端的边，其下方子树的异或和一定为 \(x\)。
简单数归可得断掉的每一条边，其下方子树异或和为 \(x\) 或 \(0\)（那么显然有解的充要条件是 \(s_1=0\lor s_1=x\)）。考虑树形 DP，令 \(f_{u,0/1}\) 表示当前 DP 到 \(u\) 子树头上那条边，它连接了一个异或和为 \(s_u\) （或 \(s_u\oplus x\)）的连通块的合法方案数，分别代表已经『断』掉了偶数 / 奇数个合法连通块。
首先自然可以一条边都不断，\(f_{u,0}=1\)。那么更新就应为：
\[ f'_{u,0}=f_{u,0}\cdot f_{v,0}+f_{u,1}\cdot f_{v,1}\\ f'_{u,1}=f_{u,0}\cdot f_{v,1}+f_{u,1}\cdot f_{v,0} \]
接着，如果 \(s_u\) 恰好为 \(0\) 或 \(x\)，这条边连接的连通块的异或和就可以是 \(x\)，那么就可以在这条边处断开，提供一个空连通块（加入异或和为 \(0\) 的方案）。
最后注意 \(x\) 可能为 \(0\)，需要特殊处理——每个 \(s_u=0\) 处都可以断开。
这个 DP 状态实在非常新奇；同时 DP 和删边又是分开的，显得非常割裂。看 sol、听 grisses 讲解的时候都完全一头雾水。quack 说这是因为我没做过连通块 DP /ll
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("ex_town1.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1), s(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::function<void(int, int)> DFS = [&](int x, int fa) {
s[x] = a[x];
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
s[x] ^= s[i];
}
return;
};
DFS(1, -1);
if (s[1] != 0 && s[1] != m) {
std::cout << 0 << '\n';
return 0;
}
if (m == 0) {
auto res(1ll);
for (int i = 2; i <= n; ++i)
if (s[i] == 0)
(res *= 2) %= mod;
std::cout << res << '\n';
}
else {
std::vector<std::array<long long, 2> > f(n + 1);
DFS = [&](int x, int fa) {
f[x][0] = 1ll;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
std::tie(f[x][0], f[x][1]) = std::make_tuple((f[x][0] * f[i][0] + f[x][1] * f[i][1]) % mod, (f[x][0] * f[i][1] + f[x][1] * f[i][0]) % mod);
}
if (x != 1) {
if (s[x] == m)
(f[x][1] += f[x][0]) %= mod;
if (s[x] == 0)
(f[x][0] += f[x][1]) %= mod;
}
// printf("f[%d][0] = %lld, f[%d][1] = %lld\n", x, f[x][0], x, f[x][1]);
return;
};
DFS(1, -1);
std::cout << (s[1] == m ? f[1][0] : f[1][1]) << '\n';
}
return 0;
}perm
http://222.180.160.110:61235/contest/6407/problem/3
给定一个长度为 \(n\)、元素两两不同的序列，你可以交换任意两个元素。试使用最少交换次数使得序列有序，问方案数。
\(n\le 10^6\)。
对于一个下标，将它和它上面元素的 rank 连有向边，那么每个下标的出、入度都为 \(1\)，则图由若干个简单环组成。
接着，考虑一次任意一次交换 \((x,y)\) 的操作会带来什么：
若 \(x,y\) 不在同一环上：
该操作使得 \(x,y\) 所在的环合为一个大环。若 \(x,y\) 在同一环上：
该操作使得环以 \(x,y\) 为分界线裂成两个小环。
以得到 \(n\) 个自环为目标，数归得到，对于最优方案，当且仅当每次交换的目标都在同一环上。
考虑方案数。把一个大小为 \(k\) 的环，欲将其拆成 \(k\) 个自环，共需 \(k-1\) 次 有序 的拆解。
考虑 DP，令 \(f_k\) 为方案数，那么 \(f_k=\dfrac {k\sum\limits_{j=1}^{k-1} f_j\cdot f_{k-j}\cdot C_{k-2}^j}2\)。尝试打表，（惊讶地）发现 \(f_k=k^{k-2}\)。
不同的环之间的操作可以交错，看作多重集排列即可。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n + 1), p(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], p[i] = i;
std::sort(p.begin() + 1, p.end(), [&](int i, int j) { return a[i] < a[j]; });
std::vector<int> f(n + 1), siz(n + 1, 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
auto merge = [&](int x, int y) {
x = find(x), y = find(y);
if (x != y)
siz[y] += siz[x], f[x] = y;
return;
};
for (int i = 1; i <= n; ++i)
merge(i, p[i]);
std::vector<long long> g(n + 1), fac(n + 1), inv(n + 1);
g[1] = g[2] = 1ll, fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [&](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
for (int i = 3; i <= n; ++i)
g[i] = qkp(i, i - 2);
int cnt(0);
auto res(1ll);
for (int i = 1; i <= n; ++i)
if (f[i] == i) {
cnt += siz[i] - 1;
(res *= g[siz[i]]) %= mod;
(res *= inv[siz[i] - 1]) %= mod;
}
(res *= fac[cnt]) %= mod;
std::cout << res << '\n';
return 0;
}CF2122D Traffic Lights
https://codeforces.com/contest/2122/problem/D
给你一个由 \(n\) 个顶点和 \(m\) 条边组成的简单无向连通图。在顶点 \(1\) 有一个标记。认为初始时间为 \(t=0\)，在 \(t\) 秒后，如果标记位于点 \(u\) ，则必须执行以下操作之一：
- 等待一秒。
- 将标记沿 \(u\) 的第 \((t \bmod \mathrm{deg}(u) + 1)\) 条边移动，花费一秒。
计算将标记从顶点 \(1\) 移到顶点 \(n\) 所需的最短时间，以及在使总时间最小化的同时所能达到的最短等待时间。\(m\le 5\times 10^5\)。
能够发现这是一个边权和 dis 有关的最短路，本着分层图一类的想法，考察答案的最值。发现一个很松的上界是 \(O(m)\)；发现实际情况会比这个乐观得多，这个时候就会考虑用一些暴力做法草过去了。
实际上有一个上界是 \(3n\)：取一条最短路，则不存在路径外的点，与路径上至少四个点有连边，否则可以更新最短路。设最短路长 \(k\)，让每次等待时间取满，考察答案发现为 \(2k\)（路径上点之间）、\(3(n-k)\)（路径上与路径外），共为 \(\le 3n\)。还有一个上确界是 \(2n-3\)，可以欣赏一下 https://codeforces.com/blog/entry/144876?#comment-1295568，我没看懂 😰
总之可以猜到暴力 dij 上 DP 得到…… 啊题解怎么说是 \(O(n^2+m)\) 的。原因是求得答案上界之后就能暴力模拟这个过程了 😅
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g(n + 1);
for (int x, y; m--; ) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<std::vector<int> > dis(2, std::vector<int> (n + 1, inf));
dis[1][1] = 0;
for (int t = 0; ; ++t) {
auto &d = dis[t & 1], &la = dis[(t & 1) ^ 1];
std::vector<int> (n + 1, inf).swap(d);
for (int i = 1; i <= n; ++i) {
int to = t % ((int)g[i].size());
d[g[i][to]] = std::min(d[g[i][to]], la[i]);
d[i] = std::min(d[i], la[i] + 1);
}
if (d[n] != inf) {
std::cout << t + 1 << ' ' << d[n] << '\n';
break;
}
}
}
return 0;
}ARC202A Merge and Increment
https://atcoder.jp/contests/arc202/tasks/arc202_a
假设相邻元素全部不同，至少在当前这一步有一个很显然的策略（记为 策略一）是选全局最小值，把它和它左边、右边更小的一个 merge 起来。
注意到如果当前全局最小值有相邻的偶数个，可以把相邻项合并一次，得到长度减半的区间，一定不劣（记为 策略二）；假如当前全局最小值存在相邻的奇数个，很容易注意到有两种处理方式：
- 选取偶数个应用策略二，剩余一个应用策略一。
- 花一步，补一个全局最小值，转化为策略二。
很容易发现第二种方式一定不劣 😅。模拟即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (std::cin >> T; T--; ) {
int n;
std::cin >> n;
std::vector<std::pair<int, int> > a(1);
{
for (int i = 1, x; i <= n; ++i) {
std::cin >> x;
if (x != a.back().first)
a.emplace_back(x, 1);
else
++a.back().second;
}
n = (int)a.size() - 1;
}
std::vector<int> pre(n + 2), nex(n + 1), tag(n + 1);
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > q;
for (int i = 1; i <= n; ++i) {
q.emplace(a[i].first, i);
pre[i] = i - 1, nex[i] = i + 1;
}
nex[0] = 1, pre[n + 1] = n;
auto del = [&](int i) {
tag[i] = 1;
pre[nex[i]] = pre[i], nex[pre[i]] = nex[i];
return;
};
auto res(0ll);
for (; (int)q.size() > 1;) {
auto [x, id] = q.top();
q.pop();
if (tag[id] || a[id].first != x)
continue;
if (a[id].second == 1) {
if (!pre[id] || (nex[id] != n + 1 && a[nex[id]].first <= a[pre[id]].first))
res += a[nex[id]].first - x, a[id].first = a[nex[id]].first;
else
res += a[pre[id]].first - x, a[id].first = a[pre[id]].first;
}
else {
if (a[id].second & 1)
++res, ++a[id].second;
++a[id].first, a[id].second /= 2;
}
if (pre[id] && a[id].first == a[pre[id]].first)
a[id].second += a[pre[id]].second, del(pre[id]);
if (nex[id] != n + 1 && a[id].first == a[nex[id]].first)
a[id].second += a[nex[id]].second, del(nex[id]);
q.emplace(a[id].first, id);
}
{
auto [x, id] = q.top();
for ( ; a[id].second != 1; ) {
if (a[id].second & 1)
++res, ++a[id].second;
++a[id].first, a[id].second /= 2;
}
}
std::cout << res << '\n';
}
return 0;
}