AtCoder Grand Contest 039 题解

AtCoder Grand Contest 039

Connection and Disconnection

分类讨论贪心。

const int N = 107;
int n, c, k, t, a, b;
char s[N];

int main() {
	rds(s, n), rd(k);
	for (int l = 1, r = 1; l <= n; l = ++r) {
		while (s[r+1] == s[l]) ++r;
		t += (r - l + 1) >> 1, ++c;
		if (!a) a = r - l + 1;
		b = r - l + 1;
	}
	if (s[1] != s[n]) print(1ll * k * t);
	else if (c == 1) print((1ll * n * k) >> 1);
	else {
		t -= (a >> 1) + (b >> 1);
		t += (a + b) >> 1;
		print(1ll * k * t - ((a & 1) && (b & 1)));
	}
	return 0;
}

Graph Partition

首先图要是一张二分图。

是二分图的情况下，从某一个点开始 bfs，如果合法，用最大深度更新答案即可。

时间复杂度 $\mathcal O(n^3)$ 。

const int N = 207;
int n, c[N], d[N], ans;
vi e[N];

void dfs(int x, int o) {
	c[x] = o;
	for (int y : e[x])
		if (!c[y]) dfs(y, 3 - o);
		else if (c[x] == c[y]) print(-1), exit(0);
}

inline int calc(int s) {
	for (int i = 1; i <= n; i++) d[i] = 0;
	d[s] = 1;
	queue<int> q;
	q.push(s);
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int y : e[x])
			if (!d[y]) d[y] = d[x] + 1, q.push(y);
			else if (d[y] != d[x] - 1 && d[y] != d[x] + 1) return 0;
	}
	return *max_element(d + 1, d + n + 1);
}

int main() {
	rd(n);
	for (int x = 1; x <= n; x++)
		for (int y = 1; y <= n; y++) {
			char c;
			rdc(c);
			if (c == '1') e[x].pb(y);
		}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) ans = max(ans, calc(i));
	print(ans);
	return 0;
}

Division by Two with Something

有趣的计数题。

不当成一个 $n$ 位二进制数而看作一个 $0/1$ 串的话，每次操作相当于把最右边的字符取反放到最左边。

考虑一个 $0/1$ 串如何计算需要多少次操作能回到本身。

首先注意到串 $s$ 一定会至多经过 $n$ 次操作完全取反，然后再经过同等次数的操作回到本身。

因此任何一个串一定能够回到本身，且次数不超过 $2n$ 次，且次数为偶数次。

假设次数为 $2t$ 次，则意味着 $t$ 次之后能取反。

于是有 $s[n-t+1:n]$ 和 $s[n-2t+1:n-t]$ 互反， $s[n-2t+1:n-t]$ 和 $s[n-3t+1:n-2t]$ 互反， $\cdots$ ， $s[t+1:2t]$ 与 $s[1:t]$ 互反， $s[1:t]$ 与 $s[n-t+1:n]$ 互反。

因此 $t$ 为满足：

$n$ 的约数；
$\frac nt$ 为奇数；
$s[i]$ 与 $s[i+t]$ 互反；

的最小值。

于是就简单了，枚举 $t$ ，求出恰好经过 $t$ 次操作回到本身且 $\le X$ 的个数，即：

$S[1:t]$ 所构成的数；
减去 $t$ 的约数对应的个数（这意味着更小的循环节）；
如果 $S[1:t]$ 根据 $s[i]$ 与 $s[i+t]$ 互反，扩展成长度为 $n$ 的数之后 $\le X$ ，则还要加上 $1$ 。

然后将个数乘上 $2t$ 就是 $t$ 的贡献。

时间复杂度 $\mathcal O(n \sqrt n)$ 。

const int N = 2e5 + 7;
int n;
char s[N];
bool a[N], b[N];
modint c[N], ans;

inline bool pd(int i) {
	for (int j = 1; j <= i; j++) b[j] = a[j];
	for (int j = i + 1; j <= n; j++) {
		b[j] = b[j-i] ^ 1;
		if (b[j] < a[j]) return 1;
		if (b[j] > a[j]) return 0;
	}
	return 1;
}

int main() {
	rd(n), rds(s, n);
	for (int i = 1; i <= n; i++) a[i] = s[i] & 15;
	for (int i = 1; i <= n; i++)
		if (!(n % i) && ((n / i) & 1)) {
			for (int j = 1; j <= i; j++)
				c[i] = c[i] * 2 + a[j];
			for (int j = 1; j < i; j++)
				if (!(i % j)) c[i] -= c[j];
			c[i] += pd(i);
			ans += c[i] * i * 2;
		}
	print(ans);
	return 0;
}

Incenters

题意

平面直角坐标系上有 $n$ 个点，第 $i$ 个点为 $(\cos(\frac {2\pi T_i}{L}), \sin(\frac {2\pi T_i}{L}))$ 。
求出在 $n$ 个点中随机选择三个点，以这三个点为顶点的三角形的内心的期望坐标。
$n \le 3 \times 10^3$ ， $0 \le T_i < L \le 10^9$ 。

题解

对于 $\triangle ABC$ ，取 $AB,BC,CA$ 弧的中点 $D,E,F$ ，可以发现 $\triangle DEF$ 的垂心就是 $\triangle ABC$ 的内心。

考虑如何求 $\triangle DEF$ 的垂心，根据欧拉线，由于 $\triangle DEF$ 的外心为 $O(0,0)$ ，重心为 $\frac{D+E+F}{3}$ ，所以垂心为 $D+E+F$ 。

于是显然可以 $\mathcal O(n^2)$ 枚举求答案。

代码

const int N = 3e3 + 7;
const ld PI = acos(-1);
int n, L, a[N];
ld x, y;

int main() {
	rd(n, L), rda(a, n);
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
			x += (n - 2 * (j - i)) * cos(PI * (a[i] + a[j]) / L),
			y += (n - 2 * (j - i)) * sin(PI * (a[i] + a[j]) / L);
	ll k = 1ll * n * (n - 1) * (n - 2) / 6;
	printf("%.20Lf %.20Lf\n", x / k, y / k);
	return 0;
}

Pairing Points

题意

圆上有 $2n$ 个点，对于任意六个点 $a,b,c,d,e,f$ 满足 $ab,cd,ef$ 三线不共点。
给定一个 $2n \times 2n$ 的 $0/1$ 矩阵 $a$ ，你需要计算将 $2n$ 个点分成 $n$ 个点对的方案数，满足：
- 对于所有点对 $(p,q)$ ， $a_{p,q} = a_{q,p} = 1$ 。
- 将所有点对用线段连接起来，恰好形成一棵树。
$n \le 20$ 。

题解

考虑先将 $n$ 设为原本的 $2n$ 。

考虑用 $f(l,m,r)$ 表示在 $[l,m-1] \cup [m+1,r]$ 中连一些点对，使得至少有一组点对跨过 $m$ ，且所有跨过 $m$ 的点对两两不交的方案数。

枚举 $1$ 号点的对应点 $i$ ，于是问题求 $f(2,i,n)$ 的答案。

考虑如何求 $f(l,m,r)$ ，枚举跨过 $m$ 的所有点对中最靠近 $l,r$ 的点对 $(p,q)$ 。

可以发现，此时 $[p+1,m-1]$ 中，有靠近 $p$ 的一部分会和 $p$ 连通，剩下的部分与 $m$ 连通，分界点为 $x$ 。

同理，此时 $[m+1,q-1]$ 中，有靠近 $q$ 的一部分会和 $q$ 连通，剩下的部分与 $m$ 连通，分界点为 $y$ 。

而 $[l,p-1]$ 一定和 $p$ 连通， $[q+1,r]$ 一定和 $q$ 连通。

因此问题被分为了 $f(l,p,x),f(y,q,r),f(x+1,m,y-1)$ 三个子问题。

记忆化搜索即可，状态数为 $\mathcal O(n^3)$ ，转移为 $\mathcal O(n^4)$ ，总时间复杂度为 $\mathcal O(n^7)$ ，常数非常小，可以通过本题。

这个 DP 可以优化到 $\mathcal O(n^5)$ ，不过没必要。

代码

const int N = 47;
int n, a[N][N];
char s[N][N];
ll f[N][N][N], ans;
bool v[N][N][N];

ll DP(int l, int m, int r) {
	if ((l ^ r) & 1) return 0;
	if (l == m && m == r) return 1;
	if (l == m || m == r) return 0;
	if (v[l][m][r]) return f[l][m][r];
	v[l][m][r] = 1;
	for (int p = l; p < m; p++)
		for (int q = r; q > m; q--)
			if (a[p][q])
				for (int x = p; x < m; x++)
					for (int y = q; y > m; y--)
						f[l][m][r] += DP(l, p, x) * DP(y, q, r) * DP(x + 1, m, y - 1);
	return f[l][m][r];
}

int main() {
	rd(n), n <<= 1;
	for (int i = 1; i <= n; i++) rds(s[i], n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = s[i][j] & 1;
	for (int i = 2; i <= n; i++)
		if (a[1][i]) ans += DP(2, i, n);
	print(ans);
	return 0;
}

Min Product Sum

题意

有一个 $n \times m$ 的矩阵 $a$ ，每个位置上有一个 $[1,k]$ 的整数。
对于一种填数方案，设 $f(x,y) = \min(\min_{i=1}^n a_{i,y}, \min_{j=1}^m a_{x,j})$ ，则这种方案的权值为 $\prod_{x=1}^n \prod_{y=1}^m f(x,y)$ 。
求一共 $k^{nm}$ 种方案的权值和。
$n,m,k \le 100$ ，答案对 $P$ 取模。

题解

首先转化题意：

有两个 $n \times m$ 的矩阵 $a,b$ ，每个位置上有一个 $[1,k]$ 的整数。
另外要求 $b_{x,y} \le \min(\min_{i=1}^n a_{i,y}, \min_{j=1}^m a_{x,j})$ 。
求方案数。

显然这两者是等价的。

设 $x_i = \min_{j=1}^m a_{i,j}$ ， $y_j = \min_{i=1}^n a_{i,j}$ ，假设我们已经设定了所有 $x_i,y_j$ ，考虑如何求方案数。

对于 $a$ ， $a_{i,j}$ 可以填 $[\max(x_i, y_j), k]$ ；对于 $b$ ， $b_{i,j}$ 可以填 $[1,\min(x_i,y_i)]$ 。

然而这样填是有问题的，并不能保证最小值恰好 $x_i,y_j$ ，于是需要容斥一下，即枚举有多少行多少列的最小值大于设定值，乘上 $-1$ 的那么多次方。

考虑 DP，从小到大填 $x_i,y_i$ ，设 $f_{t,i,j}$ 表示已经填了 $1 \sim t$ ，用了 $i$ 行 $j$ 列， $a$ 已经填了这 $i$ 行 $j$ 列的交的位置， $b$ 已经填了这 $i$ 行 $j$ 列的并的位置，的方案数。

转移时枚举填 $t$ 的不被容斥的行列数 $p,q$ ，被容斥的行列数 $u,v$ ，则有： $f_{t,i+p+u,j+q+v} \leftarrow (-1)^{u+v} \binom {n-i}{p,u} \binom {m-j}{q,v} \cdot (k-t+1)^{iq+pj+pq}(k-t)^{iv+pv+uj+uq+uv}t^{(p+u)(m-j)+(n-i)(q+v)-(p+u)(q+v)} \cdot f_{t-1,i,j}$ 然而设 $n,m,k$ 同阶，这个 DP 复杂度是 $\mathcal O(n^7)$ ，显然要优化。

依然从小到大枚举 $t$ ，在这一层转移时，可以发现我们不必同时枚举 $p,q,u,v$ ，而只需要依次枚举，每次把贡献计算清楚即可。

具体而言，先让 $f_t$ 继承 $f_{t-1}$ 。

再枚举 $p$ ，转移为： $f_{t,i+p,j} \leftarrow \binom {n-i}{p} \cdot (k-t+1)^{pj}t^{p(m-j)} \cdot f_{t,i,j}$ 再枚举 $q$ ，转移为： $f_{t,i,j+q} \leftarrow \binom {m-j}{q} \cdot (k-t+1)^{iq}t^{q(n-i)} \cdot f_{t,i,j}$ 再枚举 $u$ ，转移为： $f_{t,i+u,j} \leftarrow (-1)^u\binom {n-i}{u} \cdot (k-t)^{uj}t^{u(m-j)} \cdot f_{t,i,j}$ 再枚举 $v$ ，转移为： $f_{t,i,j+v} \leftarrow (-1)^v\binom {m-j}{v} \cdot (k-t)^{iv}t^{v(n-i)} \cdot f_{t,i,j}$ 时间复杂度 $\mathcal O(n^4)$ ，很卡常，要进行一定程度的预处理，尽可能减少取模次数。

代码

const int N = 107;
int n, m, k;
int f[N<<2][N][N], g[N][N*N], c[N][N];

inline void upd(int &x, int y, int z) {
	x = (x + 1ll * y * z) % P;
}

int main() {
	rd(n, m, k), rd(P);
	init(max(n, m));
	for (int i = 0; i <= k; i++) {
		g[i][0] = 1;
		for (int j = 1; j <= n * m; j++) g[i][j] = 1ll * g[i][j-1] * i % P;
	}
	for (int i = 0; i <= max(n, m); i++)
		for (int j = 0; j <= i; j++) c[i][j] = binom(i, j).x;
	f[0][0][0] = 1;
	for (int t = 1, o = 0; t <= k; t++) {
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
				if (!!f[o][i][j]) {
					ll x = f[o][i][j], y = 1ll * g[k-t+1][j] * g[t][m-j] % P;
					for (int p = 0; i + p <= n; p++, (x *= y) %= P) upd(f[o+1][i+p][j], c[n-i][p], x);
				}
		++o;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
				if (!!f[o][i][j]) {
					ll x = f[o][i][j], y = 1ll * g[k-t+1][i] * g[t][n-i] % P;
					for (int q = 0; j + q <= m; q++, (x *= y) %= P) upd(f[o+1][i][j+q], c[m-j][q], x);
				}
		++o;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
				if (!!f[o][i][j]) {
					ll x = f[o][i][j], y = P - 1ll * g[k-t][j] * g[t][m-j] % P;
					for (int u = 0; i + u <= n; u++, (x *= y) %= P) upd(f[o+1][i+u][j], c[n-i][u], x);
				}
		++o;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
				if (!!f[o][i][j]) {
					ll x = f[o][i][j], y = P - 1ll * g[k-t][i] * g[t][n-i] % P;
					for (int v = 0; j + v <= m; v++, (x *= y) %= P) upd(f[o+1][i][j+v], c[m-j][v], x);
				}
		++o;
	}
	print(f[k<<2][n][m]);
	return 0;
}