AtCoder Grand Contest 039 题解
Visits: 368
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;
}
