好消息：会简单数学题 
更好的消息：忘取模了
A. distorted
http://222.180.160.110:61235/contest/5611/problem/1
考虑最多需要多少个元素。最坏情况是选取四个角的元素，已经可以覆盖整个矩阵。进一步考虑感性反证发现无论如何都选不出来五个，故最多选择四个。
我们发现，选取中间一个就可以覆盖整个矩阵。扩展一下，选择中间列就可以覆盖上 / 下半个矩阵，选择中间行就可以覆盖左 / 右半个矩阵。剩下的选择过后只能保证照顾到对应的 1/4 矩阵且一定不会完全覆盖其他的 1/4 矩阵。
我们发现，中心元素地位高于中间行 / 列元素高于左上、左下、右上、右下元素。由此出发讨论选择元素的个数。
- 1 个：选择中心元素。
- 2 个：在中间行的左右两边各选一个 / 在中间列的上下两边各选一个。
- 3 个：选一个中间行 / 列 + 两个其他元素，或两个中间行 / 列 + 一个其他元素。
- 4 个：左上、左下、右上、右下各选一个。
统计各个方向的最小值，选最小组合即可。
#include <bits/stdc++.h>
#define putchar
const long long inf = 0x3f3f3f3f;
int main() {
freopen("distorted.in", "r", stdin);
freopen("distorted.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int T;
for (std::cin >> T; T--; ) {
int n;
std::cin >> n;
long long to = inf, u = inf, d = inf, l = inf, r = inf, q = inf, z = inf, p = inf, m = inf;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
long long x;
std::cin >> x;
if (i * 2 - 1 == n && j * 2 - 1 == n)
to = x;
else if (i * 2 - 1 == n && j * 2 - 1 < n)
l = std::min(l, x);
else if (i * 2 - 1 == n)
r = std::min(r, x);
else if (i * 2 - 1 < n && j * 2 - 1 == n)
u = std::min(u, x);
else if (j * 2 - 1 == n)
d = std::min(d, x);
else if (i * 2 - 1 < n && j * 2 - 1 < n)
q = std::min(q, x);
else if (i * 2 - 1 < n)
p = std::min(p, x);
else if (j * 2 - 1 < n)
z = std::min(z, x);
else
m = std::min(m, x);
}
std::cout << std::min({ to, l + r, u + d, l + u + m, l + d + p, r + u + z, r + d + q, u + z + m, d + q + p, l + p + m, r + q + z, q + p + z + m }) << '\n';
}
return 0;
}B. fate
http://222.180.160.110:61235/contest/5611/problem/2
诈骗题。对于前半段，考虑取差分数组 \(d\)，容易发现如果直接在差分数组上做减法，一定满足后面减得不比前面少。故只要满足差分数组每一项至少为 \(0\) 即可，答案为 \(\prod {i\le p} a_i - a_{i-1} + 1\)。
对于后半段，我们考虑转化成和前半段相似的问题，将后半段翻转，同样取差分数组，则此时在该差分数组上满足后面减得不比前面少，同时需要满足差分数组每一项至多为 \(0\)，前面的所有项初始为负，操作为减，自然满足；但第 \(p\) 项在把前面减去的全部加上后不一定满足。故前面最多减去 \(d_p\)，随便在哪里减都无所谓，组合意义一下，就是无标号球放有标号盒子可空放可不放，插板得答案为 \(\displaystyle {-d_p + n - p\choose n - p}\)。
前后乘起来即为答案。注意不要在最后一部乘起来的时候忘记取模，否则你会获得
76pts 的高分 
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
freopen("fate.in", "r", stdin);
freopen("fate.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int n, m;
std::cin >> n;
std::vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::cin >> m;
long long res = 1;
for (int i = 1; i < m; ++i) {
auto x = a[i] - a[i - 1];
(res *= x + 1) %= mod;
}
auto qkp = [](long long x, int y) {
long long res = 1;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
auto C = [&](int n, int m) {
long long res = 1ll;
for (int i = n; i > n - m; --i)
(res *= i) %= mod;
for (int i = m; i; --i)
(res *= qkp(i, mod - 2)) %= mod;
return res;
};
if (m != n)
(res *= C(a[m + 1] - a[m] + n - m, n - m)) %= mod;
std::cout << res << '\n';
return 0;
}C. abstruse
https://www.luogu.com.cn/problem/P9731
注意到有挺高的一档 \(S=2\) 的份，考虑其启示意义。
我们对于一对 \((a_i, b_i)\)，在 \(a_i\) 和 \(b_i\) 间连边，则原问题转化为给无向图的每条边选择方向，使对于每个 \(x\)，\(|in_x-out_x|\le 1\)。
我们知道对于一条欧拉回路，有对于任意 \(x\)，\(in_x=out_x\)。然后这个时候为了把问题转化成欧拉回路问题我们建一个虚点朝度数为奇的点连条边然后跑欧拉回路即可。
至于 \(S=2^k\)，就是在明示分治。即对于任意 \(x\)，要求其在前后 \(2^{k-1}\) 次出现次数相差不超过 \(1\)。注意到非常幸福的有前后两个部分大小相等，又有一个天才的建图，即在每个点和自己所属的行连边，然后跑欧拉回路，出边表示选前半部分，入边表示选后半部分，这样就保证了一行中各有 \(2^{k-1}\) 个选前后半部分，也保证了每个点在前后半边出现的次数相差不超过 \(1\)。对于后面一个性质，分治最终可得到点在每一列出现次数相差不超过 \(1\)。
打个当前弧优化然后注意计算细节复杂度然后多卡几（十）遍就过了
#include <bits/stdc++.h>
namespace fastIO {
const int LEN = (1 << 20);
#ifdef ONLINE_JUDGE
int nec(void) {
static char buf[LEN], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, LEN, stdin);
if (e == buf) return EOF;
p = buf;
}
return *p++;
}
#else
#define nec getchar
#endif
bool read(int &x) {
x = 0;
bool f = 0;
char ch = nec();
while (ch < '0' || ch > '9') {
if (ch == EOF) return 0;
if (ch == '-') f = 1;
ch = nec();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = nec();
}
if (f) x = -x;
return 1;
}
void print(int x) {
if (x < 0)
putchar('-'), x = -x;
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
return;
}
void print(int x, char ch) {
print(x), putchar(ch);
return;
}
} using namespace fastIO;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
freopen("abstruse.in", "r", stdin);
freopen("abstruse.out", "w", stdout);
#else
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
int n, m, k;
read(n), read(m), read(k);
std::vector<std::vector<int> > a(n + 1, std::vector<int> (m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
read(a[i][j]);
std::vector<int> to(k + n + 1), tag(n * m + n + k + 1);
std::vector<std::vector<std::pair<int, int> > > g(k + n + 1);
std::function<void(int, int)> calc = [&](int l, int r) {
if (l + 1 == r) {
for (int i = 1; i <= n; ++i) {
g[a[i][l]].emplace_back(a[i][r], i);
g[a[i][r]].emplace_back(a[i][l], i);
}
int cnt = n;
for (int i = 1; i <= n; ++i) {
if ((int)g[a[i][l]].size() & 1)
g[0].emplace_back(a[i][l], ++cnt), g[a[i][l]].emplace_back(0, cnt);
if ((int)g[a[i][r]].size() & 1)
g[0].emplace_back(a[i][r], ++cnt), g[a[i][r]].emplace_back(0, cnt);
}
std::function<void(int)> DFS = [&](int x) {
for (int i = to[x]; i < (int)g[x].size(); i = to[x]) {
to[x] = i + 1;
auto [v, id] = g[x][i];
if (!tag[id]) {
tag[id] = 1;
if (x && v)
a[id][l] = x, a[id][r] = v;
DFS(v);
}
}
return;
};
DFS(0);
for (int i = 1; i <= n; ++i)
DFS(a[i][l]), DFS(a[i][r]);
to[0] = 0, g[0].clear();
for (int i = 1; i <= n; ++i) {
to[a[i][l]] = 0, g[a[i][l]].clear();
to[a[i][r]] = 0, g[a[i][r]].clear();
}
std::fill(tag.begin() + 1, tag.begin() + cnt + 1, 0);
return;
}
int mid = (l + r) >> 1, cnt = 0;
std::vector<std::vector<std::pair<int, int> > > g(k + n + 1);
for (int i = 1; i <= n; ++i)
for (int j = l; j <= r; ++j) {
g[a[i][j]].emplace_back(i + k, ++cnt);
g[i + k].emplace_back(a[i][j], cnt);
}
for (int i = 1; i <= n; ++i)
for (int j = l; j <= r; ++j)
if ((int)g[a[i][j]].size() & 1)
g[0].emplace_back(a[i][j], ++cnt), g[a[i][j]].emplace_back(0, cnt);
std::vector<int> L(n + 1, l - 1), R(n + 1, r + 1);
std::function<void(int)> DFS = [&](int x) {
for (int i = to[x]; i < (int)g[x].size(); i = to[x]) {
to[x] = i + 1;
auto [v, id] = g[x][i];
if (!tag[id]) {
tag[id] = 1;
if (x && v) {
if (v <= k)
a[x - k][++L[x - k]] = v;
else
a[v - k][--R[v - k]] = x;
}
DFS(v);
}
}
return;
};
DFS(0);
for (int i = 1; i <= n; ++i)
DFS(i + k);
for (int i = 1; i <= n; ++i)
for (int j = l; j <= r; ++j)
DFS(a[i][j]);
to[0] = 0, g[0].clear();
for (int i = 1; i <= n; ++i)
to[i + k] = 0, g[i + k].clear();
for (int i = 1; i <= n; ++i)
for (int j = l; j <= r; ++j)
to[a[i][j]] = 0, g[a[i][j]].clear();
std::fill(tag.begin() + 1, tag.begin() + cnt + 1, 0);
calc(l, mid), calc(mid + 1, r);
return;
};
calc(1, m);
for (int i = 1; i <= n; ++i, putchar('\n'))
for (int j = 1; j <= m; ++j)
print(a[i][j], ' ');
return 0;
}