题目传送门：AtCoder Regular Contest 107。

目录

• A - Simple Math
• B - Quadruple
• C - Shuffle Permutation
• D - Number of Multisets
• E - Mex Mat
• F - Sum of Abs

A - Simple Math

求和号的性质。时间复杂度为 \(\mathcal O (1)\)。

#include <cstdio>

typedef long long LL;
const int Mod = 998244353;

inline LL S(LL x) { return x * (x + 1) / 2 % Mod; }

int main() {
	int A, B, C;
	scanf("%d%d%d", &A, &B, &C);
	printf("%lld\n", S(A) * S(B) % Mod * S(C) % Mod);
	return 0;
}

B - Quadruple

令 \(f(x)\) 为满足 \(1 \le a, b \le N\) 和 \(a + b = x\) 的数对 \((a, b)\) 的数量，可以 \(\mathcal O (1)\) 计算。

答案为 \(\displaystyle \sum_{x = 2}^{2 N} f(x) f(x + K)\)。时间复杂度为 \(\mathcal O (N)\)。

#include <cstdio>

typedef long long LL;

int N, K;
LL Ans;

inline int f(int x) {
	return x < 2 || x > 2 * N ? 0 : x <= N + 1 ? x - 1 : 2 * N + 1 - x;
}

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 2; i <= 2 * N; ++i)
		Ans += (LL)f(i) * f(i + K);
	printf("%lld\n", Ans);
	return 0;
}

C - Shuffle Permutation

注意任意两行交换不会影响列交换的条件的真假性，反之亦然。

对两个能交换的行之间连边，则每个连通块内均可任意交换，贡献 \(c!\)，其中 \(c\) 为连通块大小。

对列同样处理。时间复杂度为 \(\mathcal O (N^3)\)。

#include <cstdio>
#include <vector>

typedef long long LL;
const int Mod = 998244353;
const int MN = 55;

int N, K, A[MN][MN], Ans;
std::vector<int> G[MN];

int c, vis[MN];
void DFS(int u) {
	vis[u] = 1;
	Ans = (LL)Ans * ++c % Mod;
	for (int v : G[u]) if (!vis[v]) DFS(v);
}

int main() {
	scanf("%d%d", &N, &K), Ans = 1;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			scanf("%d", &A[i][j]);
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j) if (i < j) {
			int ok = 1;
			for (int k = 1; k <= N; ++k)
				if (A[i][k] + A[j][k] > K)
					ok = 0;
			if (ok)
				G[i].push_back(j),
				G[j].push_back(i);
		}
	for (int i = 1; i <= N; ++i) if (!vis[i]) c = 0, DFS(i);
	for (int i = 1; i <= N; ++i) G[i].clear(), vis[i] = 0;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j) if (i < j) {
			int ok = 1;
			for (int k = 1; k <= N; ++k)
				if (A[k][i] + A[k][j] > K)
					ok = 0;
			if (ok)
				G[i].push_back(j),
				G[j].push_back(i);
		}
	for (int i = 1; i <= N; ++i) if (!vis[i]) c = 0, DFS(i);
	printf("%d\n", Ans);
	return 0;
}

D - Number of Multisets

也就是初始时 \({0.5}^0\) 处有 \(K\) 个石子，可以把其中 \(x\) 个移到 \({0.5}^1\) 处，变成 \(2 x\) 个，然后还可以继续移到更多的 \({0.5}^p\) 处。

最终正好变成 \(N\) 个石子，也就是恰好分裂 \(N - K\) 次。

令 \(\operatorname{dp}(i, j)\) 表示恰好分裂 \(i\) 次，且现在位置有 \(j\) 个石子时的方案数。答案即是 \(\operatorname{dp}(N - K, K)\)。

如果 \(i \ge j \ge 1\)，则有 \(\displaystyle \operatorname{dp}(i, j) = 1 + \sum_{k = 1}^{j} \operatorname{dp}(i - k, 2 k) = \operatorname{dp}(i, j - 1) + \operatorname{dp}(i - j, 2 j)\)。

对于 \(i < j\) 的情况，有 \(\operatorname{dp}(i, j) = \operatorname{dp}(i, i)\)。

也就是 \(\operatorname{dp}(i, j) = \operatorname{dp}(i, j - 1) + \operatorname{dp}(i - j, \min \{ 2 j, i - j \})\)。

边界条件为 \(\operatorname{dp}(i, 0) = [i = 0]\)。时间复杂度为 \(\mathcal O (N^2)\)。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353;
const int MN = 3005;

int N, K, f[MN][MN];

int main() {
	scanf("%d%d", &N, &K), N -= K;
	f[0][0] = 1;
	for (int i = 1; i <= N; ++i) {
		f[i][0] = 0;
		for (int j = 1; j <= i; ++j)
			f[i][j] = (f[i][j - 1] + f[i - j][std::min(i - j, 2 * j)]) % Mod;
	}
	printf("%d\n", f[N][std::min(N, K)]);
	return 0;
}

E - Mex Mat

考察一个简单一些的情况，如果把 \(1, 2\) 都看作 \(1\)，运算规则是类似的，都是有 \(0\) 参与则结果非 \(0\)，否则为 \(0\)。

此时考察一个位置 \(a_{i, j}\)，其中 \(i, j\) 足够大，然后考察 \(a_{i + 1, j + 1}\) 与其的关系：

• 如果 \(a_{i, j} = 0\)，则 \(a_{i, j + 1}, a_{i + 1, j}\) 均为 \(1\)，于是 \(a_{i + 1, j + 1} = 0\)。
• 如果 \(a_{i, j} = 1\)，则如果 \(a_{i + 1, j + 1} = 0\) 则 \(a_{i, j + 1}, a_{i + 1, j}\) 均为 \(1\)，于是 \(a_{i - 1, j + 1}, a_{i + 1, j - 1}\) 均为 \(0\)，于是 \(a_{i - 1, j}, a_{i, j - 1}\) 均为 \(1\)，于是 \(a_{i, j} = 0\)，但已知 \(a_{i, j} = 1\)，导出矛盾。所以 \(a_{i + 1, j + 1} = 1\)。

也就是有 \(a_{i, j} = a_{i + 1, j + 1}\)。那么其中的 \(i, j\) 足够大是多大呢？其实是 \(i, j \ge 3\) 即可，因为上述论证中只涉及 \(i - 1\) 和 \(j - 1\) 的*转移，于是就是 \((i - 1), (j - 1) \ge 2\)，所以 \(i, j \ge 3\)。

对于引入了 \(0, 1, 2\) 三种值的情况是类似的：

• 如果 \(a_{i, j} = 0\)，则 \(a_{i, j + 1}, a_{i + 1, j}\) 均非 \(0\)，于是 \(a_{i + 1, j + 1} = 0\)。
• 如果 \(a_{i, j} = 1\)，则 \(a_{i, j + 1}, a_{i + 1, j}\) 均非 \(1\)，即为 \(0\) 或 \(2\)，所以 \(a_{i + 1, j + 1}\) 为 \(0\) 或 \(1\)，当 \(a_{i + 1, j + 1} = 0\) 时只有可能是 \(a_{i, j + 1}, a_{i + 1, j}\) 均为 \(2\)，于是 \(a_{i - 1, j + 1}, a_{i + 1, j - 1}\) 均为 \(0\)，于是 \(a_{i - 1, j}, a_{i, j - 1}\) 均非 \(0\)，于是 \(a_{i, j} = 0\)，但已知 \(a_{i, j} = 1\)，导出矛盾。所以 \(a_{i + 1, j + 1} = 1\)。
• 如果 \(a_{i, j} = 2\)，则 \(a_{i - 1, j}, a_{i, j - 1}\) 中恰有一者为 \(1\) 而另一者为 \(0\)，不失一般性，不妨令 \(a_{i - 1, j} = 0\) 而 \(a_{i, j - 1} = 1\)，则根据「若 \(a_{i, j} = 0\) 则 \(a_{i + 1, j + 1} = 0\)」有 \(a_{i, j + 1} = 0\)，又根据「若 \(a_{i, j} = 1\) 则 \(a_{i + 1, j + 1} = 1\)」有 \(a_{i + 1, j} = 1\)，于是 \(a_{i + 1, j + 1} = 2\)。

此时必须满足 \(i, j \ge 4\)，因为对「若 \(a_{i, j} = 2\) 则 \(a_{i + 1, j + 1} = 2\)」的证明中用到了对 \(a_{i - 1, j}\) 或 \(a_{i, j - 1}\) 施以的「当 \(i, j \ge 3\) 时，若 \(a_{i, j} = 1\) 则 \(a_{i + 1, j + 1} = 1\)」结论，所以对 \(i, j\) 的限制再提高 \(1\)。

只需算出所有 \(\min(i, j) \le 4\) 的 \(a_{i, j}\) 值即可，后续的值根据 \(\min(i, j) = 4\) 的那些 \(a_{i, j}\) 直接得到。

时间复杂度为 \(\mathcal O (N)\)。

#include <cstdio>
#include <vector>

inline int Mex(int x, int y) {
	if (x && y) return 0;
	if (x + y == 1) return 2;
	return 1;
}

typedef long long LL;
const int MN = 500005;

int N;
std::vector<int> A[MN];
LL Ans[3];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		A[i].resize((i <= 4 ? N : 4) + 1);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[1][i]);
	for (int i = 2; i <= N; ++i) scanf("%d", &A[i][1]);
	for (int i = 2; i <= N; ++i) {
		int lim = i <= 4 ? N : 4;
		for (int j = 2; j <= lim; ++j)
			A[i][j] = Mex(A[i - 1][j], A[i][j - 1]);
	}
	for (int i = 1; i <= N; ++i) {
		int lim = i <= 4 ? N : 4;
		for (int j = 1; j <= lim; ++j)
			++Ans[A[i][j]];
	}
	if (N > 4) {
		for (int i = 4; i < N; ++i)
			Ans[A[4][i]] += N - i;
		for (int i = 5; i < N; ++i)
			Ans[A[i][4]] += N - i;
	}
	printf("%lld %lld %lld\n", Ans[0], Ans[1], Ans[2]);
	return 0;
}

F - Sum of Abs

这题一看就很网络流，但是建图并不传统，比较神奇的最小割建图方式。

首先需要一步重要的转化：对整个连通块的取绝对值变成给每个未被删除的结点赋权 \(+1\) 或 \(-1\)，要求通过边直接相连的两点的权值必须相同。这就表达了连通块符号必须相同的意思，并且留出了连通块权值可以为负的回旋余地（Note：最大化套个绝对值的东西可以把绝对值拆掉不影响结果，可能更方便进一步转化）。

为了使用类文理分科的最小割建图，我们自然是要把所有可能的贡献先加起来，然后减去最小割代表的付费限制。

即令 \(\displaystyle \mathrm{Ans} = \sum_{i = 1}^{N} |B_i|\)，然后最终答案为 \(\mathrm{Ans} \gets \mathrm{Ans} - \operatorname{MinCut}(G)\)。

我们需要描述一个结点的三种状态，即被删除、\(+1\) 权、和 \(-1\) 权。
然后还要处理如果一条边相连的两个点权值分别为 \(+1\) 和 \(-1\) 则方案非法的条件。

考虑如下建图，拆点 \(u\) 为 \(u_1, u_2\)：\(\langle \mathrm{Source} \rangle \to u_1 \to u_2 \to \langle \mathrm{Sink} \rangle\)，割开这三条边的含义分别为 \(+1\) 权、被删除、和 \(-1\) 权。

于是边权为：

• 如果 \(B_u \ge 0\)，则权值分别为 \(0\)、\(A_u + B_u\)、和 \(2 B_u\)。
• 如果 \(B_u < 0\)，则权值分别为 \(-2 B_u\)、\(A_u - B_u\)、和 \(0\)。

对于一条边连接的两个点 \(u, v\)，连接 \(u_2 \to v_1\) 和 \(v_2 \to u_1\)，权值均为 \(+\infty\)。
此时如果割 \(\langle \mathrm{Source} \rangle \to u_1\) 和 \(v_2 \to \langle \mathrm{Sink} \rangle\) 则有路径 \(\langle \mathrm{Source} \rangle \to v_1 \to v_2 \to u_1 \to u_2 \to \langle \mathrm{Sink} \rangle\) 从而不合法。

时间复杂度为 \(\operatorname{Dinic}(|V| = 2 N + 2, |E| = 2 (N + M)) = \mathcal O (N^2 (N + M))\)。

#include <cstdio>
#include <algorithm>

namespace DinicFlows {
	const int Inf = 0x3f3f3f3f;
	const int MN = 605, MM = 1205;
	
	int N, S, T;
	int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], w[MM * 2], tot;
	
	inline void SetST(int _S, int _T) { S = _S, T = _T; }
	inline void Init(int _N) {
		N = _N, tot = 1;
		for (int i = 1; i <= N; ++i) h[i] = 0;
		SetST(_N - 1, _N);
	}
	
	inline void ins(int u, int v, int x) {
		if (tot + 1 >= MM * 2) { puts("Error : too many edges."); return ; }
		nxt[++tot] = h[u], to[tot] = v, w[tot] = x, h[u] = tot;
	}
	inline void insw(int u, int v, int w1 = Inf, int w2 = 0) {
		if (!u) u = S; if (!v) v = T;
		ins(u, v, w1), ins(v, u, w2);
	}
	
	int lv[MN], que[MN], l, r;
	
	inline bool Lvl() {
		for (int i = 1; i <= N; ++i) lv[i] = 0;
		lv[S] = 1;
		que[l = r = 1] = S;
		while (l <= r) {
			int u = que[l++];
			for (int i = h[u]; i; i = nxt[i])
				if (w[i] && !lv[to[i]]) {
					lv[to[i]] = lv[u] + 1;
					que[++r] = to[i];
				}
		}
		return lv[T] != 0;
	}
	
	int Flow(int u, int f) {
		if (u == T) return f;
		int d = 0, s = 0;
		for (int &i = iter[u]; i; i = nxt[i])
			if (w[i] && lv[to[i]] == lv[u] + 1) {
				d = Flow(to[i], std::min(f, w[i]));
				f -= d, s += d;
				w[i] -= d, w[i ^ 1] += d;
				if (!f) break;
			}
		return s;
	}
	
	inline int Dinic() {
		int Ans = 0;
		while (Lvl()) {
			for (int i = 1; i <= N; ++i) iter[i] = h[i];
			Ans += Flow(S, Inf);
		}
		return Ans;
	}
}

const int MN = 305;

int N, M, A[MN], B[MN], Ans;

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
	for (int i = 1; i <= N; ++i) scanf("%d", &B[i]);
	DinicFlows::Init(2 * N + 2);
	for (int i = 1; i <= N; ++i) {
		if (B[i] >= 0) {
			Ans += B[i];
			DinicFlows::insw(i, N + i, A[i] + B[i]);
			DinicFlows::insw(N + i, 0, 2 * B[i]);
		} else {
			Ans -= B[i];
			DinicFlows::insw(0, i, 2 * -B[i]);
			DinicFlows::insw(i, N + i, A[i] - B[i]);
		}
	}
	for (int i = 1; i <= M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		DinicFlows::insw(N + x, y);
		DinicFlows::insw(N + y, x);
	}
	printf("%d\n", Ans - DinicFlows::Dinic());
	return 0;
}