AtCoder Grand Contest 038 题解

AtCoder Grand Contest 038

01 Matrix

简单构造题。

const int N = 1e3 + 7;
int n, m, a, b;

int main() {
	rd(n, m), rd(a, b);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			printc('0' + ((i <= b && j <= a) || (i > b && j > a)));
		printc('\n');
	}
	return 0;
}

Sorting a Segment

首先判断一下有没有排序后不变的区间。

除了这些区间之外，如果两个区间排序后相同，当且仅当这两个区间相邻且左右两侧分别是 $\min$ 和 $\max$ 。

ST 表 RMQ 一下即可。

const int N = 2e5 + 7;
int n, k, a[N], ans, cnt;
vi p;
bool v[N];

int st[2][N][21];

inline void init(int *a, int n) {
	int w = log2(n);
	for (int i = 1; i <= n; i++)
		st[0][i][0] = st[1][i][0] = a[i];
	for (int i = 1; i <= w; i++)
		for (int l = 1, r = 1 << i; r <= n; l++, r++)
			st[0][l][i] = min(st[0][l][i-1], st[0][l+(1<<(i-1))][i-1]),
			st[1][l][i] = max(st[1][l][i-1], st[1][l+(1<<(i-1))][i-1]);
}

inline int Min(int l, int r) {
	int w = log2(r - l + 1);
	return min(st[0][l][w], st[0][r-(1<<w)+1][w]);
}

inline int Max(int l, int r) {
	int w = log2(r - l + 1);
	return max(st[1][l][w], st[1][r-(1<<w)+1][w]);
}

int main() {
	rd(n, k), rda(a, n);
	init(a, n);
	p.pb(1);
	for (int i = 2; i <= n; i++)
		if (a[i] < a[i-1]) p.pb(i), v[i] = 1;
	p.pb(n + 1);
	for (ui i = 1; i < p.size(); i++)
		if (p[i] - p[i-1] >= k) ans = 1;
	for (int i = 2; i < k; i++) cnt += v[i];
	for (int l = 1, r = k; r <= n; l++, r++) {
		cnt -= v[l], cnt += v[r];
		if (cnt && (l == 1 || Min(l - 1, r - 1) != a[l-1] || Max(l, r) != a[r])) ++ans;
	}
	print(ans);
	return 0;
}

LCMs

简单数论题，随便莫反一下即可。

namespace shai {
	const int N = 1e6 + 7;
	int p[N], v[N], phi[N], miu[N];

	inline void init(int n) {
		v[1] = phi[1] = miu[1] = 1;
		for (int i = 2; i <= n; i++) {
			if (!v[i]) p[++p[0]] = v[i] = i, phi[i] = i - 1, miu[i] = -1;
			for (int j = 1; j <= p[0] && i * p[j] <= n && p[j] <= v[i]; j++)
				v[i*p[j]] = p[j],
				phi[i*p[j]] = phi[i] * (p[j] - 1 + (p[j] == v[i])),
				miu[i*p[j]] = p[j] == v[i] ? 0 : -miu[i];
		}
	}
}
using shai::miu;

const int N = 2e5 + 7, M = 1e6;
int n, a[N], c[M|1];
modint s[M|1], d[M|1], ans;

int main() {
	init(M), shai::init(M);
	rd(n), rda(a, n);
	for (int i = 1; i <= n; i++) ++c[a[i]];
	for (int i = 1; i <= M; i++) {
		for (int j = i; j <= M; j += i)
			d[i] += binom(c[j], 2) * j * j + s[i] * j * c[j],
			s[i] += j * c[j] % P;
	}
	for (int i = 1; i <= M; i++) {
		modint now = 0;
		for (int j = 1; i * j <= M; j++)
			if (miu[j] > 0) now += d[i*j];
			else if (miu[j] < 0) now -= d[i*j];
		ans += now * v[i];
	}
	print(ans);
	return 0;
}

Unique Path

这题有点误导性，最重要的一点是 $(a,b,1) + (b,c,1) \not\to (a,c,1)$ 。

先考虑所有 $(x,y,0)$ 的条件，则 $x,y$ 在一棵树上，形成的图是一个森林，用并查集可以得到。

这时如果条件 $(x,y,1)$ 中的 $x,y$ 在同一棵树上，则无解。

否则，设森林中树的个数为 $c$ 。

若不存在 $(x,y,1)$ 的条件，则有解当且仅当 $c - 1 \le m - n + c \le \binom c2$ 。

若存在 $(x,y,1)$ 的条件，则有解当且仅当 $\max(3,c) \le m - n + c \le \binom c2$ 。

#define Fail prints("No"), exit(0);
const int N = 1e5 + 7;
int n, m, q, f[N], c;
vector<pi> p;
bool v[N];

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

int main() {
	rd(n, m, q);
	for (int i = 1; i <= n; i++) f[i] = i;
	for (int i = 1, x, y, z; i <= q; i++) {
		rd(x, y, z), ++x, ++y;
		if (!z) f[get(x)] = get(y);
		else p.pb(mp(x, y));
	}
	for (pi o : p)
		if (get(o.fi) == get(o.se)) Fail;
	for (int i = 1; i <= n; i++) c += !v[get(i)], v[get(i)] = 1;
	int k = m - n + c;
	if (!p.size()) prints((c - 1 <= k && k <= 1ll * c * (c - 1) / 2) ? "Yes" : "No");
	else prints((max(3, c) <= k && k <= 1ll * c * (c - 1) / 2) ? "Yes" : "No");
	return 0;
}

Gachapon

题意

有一个随机数生成器，每次可以有 $\frac {a_i}{\sum_{i=0}^{n-1}a_i}$ 的概率生成 $i$ 。
求对于每个 $i$ ，都有 $i$ 被生成了至少 $b_i$ 次的期望时间。
$n, \sum_{i=0}^{n-1} a_i, \sum_{i=0}^{n-1} b_i\le 400$ ，答案对 $998244353$ 取模。

题解

设 $\max(S)$ 表示 $S$ 中的元素被生成到规定次数的最大时间，即所有元素都被生成到规定次数的期望时间，则 $ans = E(\max(U))$ 其中 $U$ 是全集， $E$ 表示期望。

根据 Min-Max 容斥，设 $\min(S)$ 表示 $S$ 中的元素被生成到规定次数的最小时间，即至少一个元素被生成到规定次数的期望时间，有 $ans = \sum_{S \subseteq U} (-1)^{|S|+1} E(\min(S))$ 考虑如何计算 $E(\min(S))$ ，有 $E(\min(S)) = \sum_{i \in S, 0 \le x_i < b_i} P(x_i)E(x_i)$ 其中 $P(x_i)$ 表示状态 $x_i$ 的出现概率， $E(x_i)$ 表示状态 $x_i$ 的期望持续时间。

显然当 $S$ 相同时 $E(x_i)$ 都一样 $E(x_i) = \frac A{A_S}$ 为了方便，不妨认为 $a,b$ 的下标从 $1$ 开始，于是其中的 $A = \sum_{i=1}^{n} a_i$ ， $A_S = \sum_{i \in S} a_i$ 。

考虑如何求 $P(x_i)$ ，即要求 $i \in S$ 的 $i$ 恰好出现 $x_i$ 次的概率，此时不再需要考虑 $U - S$ 中的元素。

设 $X = \sum_{i \in S}x_i$ ，此时为有标号概率（设 $i,j \in S$ ，先 $i$ 后 $j$ 和先 $j$ 后 $i$ 是两种情况），因此考虑 EGF，对于 $i$ 的 EGF 为 $f_i(x) = \sum_{n \ge 0} \left(\frac {a_i}{A_S}\right)^n \frac{x^n}{n!}$ 所以 $P(x_i) = X! \prod_{i \in S} \left(\frac {a_i}{A_S}\right)^{x_i}\frac 1{x_i!}$ 整理一下，我们要算的就是这个玩意儿 $\begin{aligned} ans &= E(\max(U)) \\\\ &= \sum_{S \subseteq U} (-1)^{|S|+1} E(\min(S)) \\\\ &= \sum_{S \subseteq U} (-1)^{|S|+1} \left(\sum_{i \in S, 0 \le x_i < b_i} P(x_i)E(x_i)\right) \\\\ &= \sum_{S \subseteq U} (-1)^{|S|+1} \frac A{A_S}\sum_{i \in S, 0 \le x_i < b_i} P(x_i) \\\\ &= \sum_{S \subseteq U} (-1)^{|S|+1} \frac A{A_S}\sum_{i \in S, 0 \le x_i < b_i} X! \prod_{i \in S} \left(\frac {a_i}{A_S}\right)^{x_i}\frac 1{x_i!} \\\\ &= A\sum_{S \subseteq U} \sum_{i \in S, 0 \le x_i < b_i}(-1)^{|S|+1} \frac {X!}{A_S^{X+1}} \prod_{i \in S} \frac {a_i^{x_i}}{x_i!} \\\\ \end{aligned}$ 考虑一下 $\sum_{S \subseteq U} \sum_{i \in S, 0 \le x_i < b_i}$ 本质上枚举了啥。

其实就是对于每个 $i$ ，都可以选或者不选，如果选还要考虑选多少个。

于是显然 DP，状态中需要记录 $A_S$ 和 $X$ 的值，因此设 $f_{i,j,k}$ 表示考虑了前 $i$ 个数， $A_S = j$ ， $X = k$ 的贡献之和。

初始状态为 $f_{0,0,0} = -1$ 。

转移为 $f_{i+1,j,k} \leftarrow f_{i,j,k} \\\\ f_{i+1,j+a_{i+1},k+l} \leftarrow -(\frac{a_{i+1}^{l}}{l!}f_{i,j,k})(l < b_{i+1})$ 目标为 $ans = A\sum_{j=1}^{A}\sum_{k=0}^B \frac{k!}{j^{k+1}}f_{n,j,k}$ 其中 $B = \sum_{i=1}^{n}b_i$ 。

注意到转移类似一个背包，因此倒序枚举 $j$ 可以省掉 $i$ 这一维。

总时间复杂度 $\mathcal O(AB^2)$ 。

代码

const int N = 407;
int n, a, b, A, B;
modint f[N][N], ans;

int main() {
	init(400);
	rd(n);
	f[0][0] = P - 1;
	for (int i = 0; i < n; i++) {
		rd(a, b);
		for (int j = A; ~j; j--)
			for (int k = B; ~k; k--)
				if (f[j][k].x) {
					modint o = 1;
					for (int l = 0; l < b; l++, o *= a)
						f[j+a][k+l] -= o * vp[l] * f[j][k];
				}
		A += a, B += b;
	}
	for (int j = 1; j <= A; j++) {
		modint o = v[j];
		for (int k = 0; k <= B; k++, o *= v[j])
			if (f[j][k].x)
				ans += p[k] * o * f[j][k];
	}
	print(ans * A);
	return 0;
}

Two Permutations

题意

给定两个 $0 \sim n - 1$ 的排列 $p_{0\dots n-1},q_{0\dots n-1}$ 。
构造两个 $0 \sim n - 1$ 的排列 $a_{0\dots n-1}, b_{0\dots n-1}$ ，使得：
- $a_i = i$ 或 $a_i = p_i$ 。
- $b_i = i$ 或 $b_i = q_i$ 。
要求最大化 $\sum_{i=0}^{n-1} [a_i \ne b_i]$ 。
$n \le 10^5$ 。

题解

考虑最小化 $\sum_{i=0}^{n-1}[a_i=b_i]$ 。

显然每个循环之间相互独立，环内要么不变，要么转一格。

记 $x_i$ 表示 $i$ 在 $p$ 中的环， $v(x_i)$ 表示这个环是否转。

记 $y_i$ 表示 $i$ 在 $q$ 中的环， $v(y_i)$ 表示这个环是否转。

考虑一个 $i$ ：

若 $p_i = i$ ， $q_i = i$ ，则任何情况下都有贡献。
若 $p_i = i$ ， $q_i \ne i$ ，则当 $v(y_i) = 0$ 时有贡献。
若 $p_i \ne i$ ， $q_i = i$ ，则当 $v(x_i) = 0$ 时有贡献。
若 $p_i \ne i$ ， $q_i \ne i$ ， $p_i = q_i$ ，则当 $v(x_i) = v(y_i)$ 时有贡献。
若 $p_i \ne i$ ， $q_i \ne i$ ， $p_i \ne q_i$ ，则当 $v(x_i) = v(y_i) = 0$ 时有贡献。

发现这是一个集合划分模型：两个集合 $S,T$ ，对于一个环 $i$ ，如果 $v(i) = 0$ ，则 $i \in S$ ，否则 $i \in T$ 。

然而这样并没有办法做，集合划分模型中的约束应为两个物品不在同一个集合。

于是考虑修改一下定义：记 $y_i$ 表示 $i$ 在 $q$ 中的环， $v(y_i)$ 表示这个环是否转。

于是重新考虑一个 $i$ ：

若 $p_i = i$ ， $q_i = i$ ，则任何情况下都有贡献，我们直接扔掉这种情况。
若 $p_i = i$ ， $q_i \ne i$ ，则当 $v(y_i) = 1$ 时有贡献，连边 $(S, y_i, 1)$ 。
若 $p_i \ne i$ ， $q_i = i$ ，则当 $v(x_i) = 0$ 时有贡献，连边 $(x_i, T, 1)$ 。
若 $p_i \ne i$ ， $q_i \ne i$ ， $p_i = q_i$ ，则当 $v(x_i) \ne v(y_i)$ 时有贡献，连边 $(x_i, y_i, 1)$ ， $(y_i, x_i, 1)$ 。
若 $p_i \ne i$ ， $q_i \ne i$ ， $p_i \ne q_i$ ，则当 $v(x_i) = 0$ ， $v(y_i) = 1$ 时有贡献，连边 $(x_i,y_i,1)$ 。

跑最小割即可。

据说时间复杂度是 $\mathcal O(n \sqrt n)$ ，理由是连出来的图实际上是一张二分图，且容量均为 $1$ 。

代码

namespace Dinic {
	const int N = 2e5 + 7, M = 1e6 + 7;
	const ll inf = 1e18;
	int n, S, T, h[N], hi[N], e[M], t[M], tot, d[N];
	ll mxf, f[M];
	inline void add(int x, int y, ll z, int o = 1) {
		e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0, 0);
	}
	inline bool bfs() {
		for (int i = 1; i <= n; i++) d[i] = 0;
		queue<int> q;
		q.push(S), d[S] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (int i = h[x]; i; i = t[i]) {
				int y = e[i];
				ll z = f[i];
				if (d[y] || !z) continue;
				q.push(y), d[y] = d[x] + 1;
				if (y == T) return 1;
			}
		}
		return 0;
	}
	ll dinic(int x, ll nwf) {
		if (x == T) return nwf;
		ll rst = nwf;
		for (int &i = hi[x]; i; i = t[i]) {
			int y = e[i];
			ll z = f[i];
			if (d[y] != d[x] + 1 || !z) continue;
			ll k = dinic(y, min(z, rst));
			if (!k) d[y] = 0;
			else f[i] -= k, f[i^1] += k, rst -= k;
			if (!rst) break;
		}
		return nwf - rst;
	}
	inline void main() {
		while (bfs()) {
			for (int i = 1; i <= n; i++) hi[i] = h[i];
			ll now;
			while ((now = dinic(S, inf))) mxf += now; 
		}
	}
	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T, tot = 1, mxf = 0;
		for (int i = 1; i <= n; i++) h[i] = 0;
	}
}

const int N = 1e5 + 7;
int n, p[N], q[N];
int t = 2, S = 1, T = 2, ans;
int x[N], y[N];
bool u[N], v[N];

int main() {
	rd(n), rda(p, n), rda(q, n);
	for (int i = 1; i <= n; i++) ++p[i], ++q[i];
	for (int i = 1; i <= n; i++)
		if (!u[i]) {
			++t;
			int o = i;
			while (!u[o]) u[o] = 1, x[o] = t, o = p[o];
		}
	for (int i = 1; i <= n; i++)
		if (!v[i]) {
			++t;
			int o = i;
			while (!v[o]) v[o] = 1, y[o] = t, o = q[o];
		}
	Dinic::init(t, S, T);
	ans = n;
	for (int i = 1; i <= n; i++) {
		if (p[i] == i && q[i] == i) --ans;
		if (p[i] == i && q[i] != i) Dinic::add(S, y[i], 1);
		if (p[i] != i && q[i] == i) Dinic::add(x[i], T, 1);
		if (p[i] != i && q[i] != i && p[i] == q[i])
			Dinic::add(x[i], y[i], 1), Dinic::add(y[i], x[i], 1);
		if (p[i] != i && q[i] != i && p[i] != q[i])
			Dinic::add(x[i], y[i], 1);
	}
	Dinic::main();
	print(ans - Dinic::mxf);
	return 0;
}