AtCoder Regular Contest 163-526互联

A

只需暴力判断能否分成两部分即可。

时间复杂度 \(\mathcal{O}(n^2)\)。

B

肯定是选值域连续的一段数操作，排序后枚举区间即可。

时间复杂度 \(\mathcal{O}(n \log n)\)。

C

场上降智了 15min，我是什么 shaber 啊。

注意到 \(1 = \frac 1 n + \sum_{i < n} \frac{1}{i(i + 1)}\)，但是有可能出现 \(n = i(i + 1)\) 的情况，此时改为 \(\frac 1 2 + \frac{1}{2(2n - 3)} + \sum_{i < n - 1} \frac{1}{(2i - 1)(2i + 1)}\) 即可，在数据范围内不会出现问题。

时间复杂度 \(\mathcal{O}(n)\)。

D

经典结论是：竞赛图缩点后是一条链。其强连通分量个数相当于能选出多少个点的非空子集 \(S\)，使得 \(\forall u \in S, v \ne S\)，\(u, v\) 之间边的方向为 \(u \to v\)。

考虑把两边的点归并起来，设 \(f_{i, j, k}\) 表示前 \(i + j\) 个点有 \(i\) 个在 \(S\) 中、\(j\) 个不在 \(S\) 中，且已经有 \(k\) 条从小到大的边的方案数，转移是容易的。

时间复杂度 \(\mathcal{O}(n^4)\)。

E

什么结论题。

注意到 \(a_i \in [0, 4)\) 时，先手必胜当且仅当 恰好存在一种非 \(0\) 元素。对于 \(a_i \le 10^9\)，把它们的位两两分组，则先手必胜当且仅当存在一组位满足上面的条件，可以归纳证明正确性。

谁想得到每两位分一组考虑啊。

时间复杂度 \(\mathcal{O}(n \log V)\)，其中 \(V = 10^9\)（题外话：我之前一直使用 \(w\) 表示值域，而用 \(\omega\) 表示计算机字长，前几天被 zyf 狠狠地嘲讽了，于是之后就改成 \(V\) 了）。

F

对 \(0\) 取 \(\max\) 有一个经典的刻画方式：找到 \(y\) 坐标最小的点，将格路整体向上平移使得该点 \(y\) 恰好为 \(0\)。

xzy 题解里这句话，我场上想了 1h 没想到。

对于原问题，与 AGC049E 类似地，我们使用 slope trick，可以得到如下做法：

i64 calc(int *a, int n) {
  i64 res = 0;
  multiset <int> s;
  rep(i, 1, n) {
    s.insert(a[i]), s.insert(a[i]);
    res += *(-- s.end()) - a[i];
    s.erase(-- s.end());
  }
  return res;
}

问题可以转化为求所有情况下 \(s\) 中最终剩下的数之和。

将 \(v\) 转化为 \(\sum_{0 \le i < m} [i < v]\)，枚举 \(0 \le x < m\)，考虑所有情况下 \(s\) 中剩下的数中 \(> x\) 的数的个数总和。

这类似于一个从 \((0, 0)\) 走到 \((n, k)\) 的问题，每次可以走 \((1, \pm 1)\)，往每个方向走有一个权值，而且每走完一步纵坐标要与 \(0\) 取 \(\max\)。考虑把这个取 \(\max\) 去掉，枚举全局纵坐标最小值，则最后的个数就是纵坐标与这个最小值的差。设最小值为 \(-a\)，最后纵坐标为 \(b\)，我们把整条路经往上平移 \(a\) 个单位，起点变为 \((0, a)\)，并且增加折线必须碰到而不超过 \(y = 0\) 的限制，可以得到 \(x\) 的答案为

\[\sum_{0 \le a, b \le n} b \cdot x^{\frac{n + b - a}{2}} (m-x)^{\frac{n - b + a}{2}} (g(n, a + b) - g(n, a + b + 2)) \]

其中 \(g(n, k)\) 表示从 \((0, 0)\) 走到 \((n, k)\) 的方案数，并且枚举的 \(a, b\) 需要满足 \(2 \mid n + a + b\)。我们把折线按照 \(y = 0\) 或 \(y = -1\) 翻折，可以得到如上的式子。

注意到我们可以 \(\mathcal{O}(n \log^2 n)\) 地对于 \(i = 0, \cdots, n\) 求出

\[val_i = \sum_{x = 0} ^ {m - 1} x^i (m - x)^{n - i} \]

具体来说先分治 NTT 求出伯努利数，然后再做一次卷积求出每项自然数幂和，之后再做一次卷积即可。于是我们可以在最外层枚举 \(a, b\)，式子变为

\[\sum_{0 \le a, b \le n} b \cdot val_{\frac{n + b - a}{2}} (g(n, a + b) - g(n, a + b + 2)) \]

考虑转而枚举 \(d = b - a\)，将 \(g(n, k) = \binom{n}{\frac{n + k}{2}}\) 代入可得

\[\sum_{-n \le d \le n} \sum_{b - a = d} b \cdot val_{\frac{n - d}{2}} \left(\binom{n}{\frac{n - d}{2} + b} - \binom{n}{\frac{n - d}{2} + b + 1} \right) \]

注意到 \(\frac{n - d}{2}\) 出现多次，转而枚举 \(i = \frac{n - d}{2}\)，则 \(d = n - 2i\)，我们有

\[\sum_{0 \le i \le n} \sum_b b \cdot val_i \left(\binom{n}{i + b} - \binom{n}{i + b + 1} \right) \]

此时对 \(b\) 的范围限制变为 \(n \le b + 2i \le 2n\)。组合数比较难搞，转而枚举 \(k = i + b\)，则限制变为 \(n - k \le i \le k\)，式子变为

\[\sum_{0 \le k \le n} \left(\binom{n}{k} - \binom{n}{k + 1} \right) \sum_{n - k \le i \le k} val_i (k - i) \]

容易 \(\mathcal{O}(n)\) 求出。

时间复杂度 \(\mathcal{O}(n \log^2 n)\)，瓶颈在于求伯努利数。