• 2023.11.4
  • P9338 [JOISC 2023 Day3] Chorus
  • ABC327G Many Good Tuple Problems
• 2023.11.5
  • CF1237F Balanced Domino Placements

2023.11.4

打模拟赛，做题纪要摆一摆。

P9338 [JOISC 2023 Day3] Chorus

为了做这题把整个决策单调性的东西学了一遍，虽然最后也没用上多少吧。

首先如果存在划分数 \(\le K\) 的方案，那么一定存在 \(=K\) 的方案，那么我们就是要让最少划分数尽可能小。

先考虑对于一种固定的 AB 序列如何求出最少的划分数。考虑一个贪心的匹配方法，从前往后将每个极长 A 段与后面相应个数个 B 对应，这样就能得到最少的划分数。考虑这实际上相当于让第 \(i\) 个 A 与第 \(i\) 个 B 相匹配，并将这样的若干对 AB 划分成最少条链，使得每条链中的所有 A 都在 B 左边，定义两对 AB 之间的偏序关系为第 \(i\) 个 B 在第 \(j\) 个 A 左边，那么上述问题就是一个最少反链覆盖，根据 Dilworth 定理，这等于最长链，那么最少划分数就等于能选出的最多的两两不交的 AB 对，由于 AB 的位置都是单调递增的，这有显然的贪心做法，从前往后能选则选即可。

那么发现这个过程就可以 DP 了，考虑当前已经确定了第 \(1 \sim i\) 个 AB，选取的最后一个 B 的下一个 A 是第 \(i+1\) 个 A，那么按照贪心，下一次选择的就是第 \(i+1\) 个 A，考虑每次确定第 \(i+1\) 个 A 与 B 之间有多少个 A，这样就能确定下一次选择哪一个 A 了，假设从 \(i\) 转移到 \(j\)，那么我们需要将第 \(i + 1\) 到第 \(j\) 个 A 移动到第 \(i\) 个 B 的后面，那么考虑设 \(b_i\) 表示第 \(i\) 个 A 前面有 \(b_i\) 个 B，则移动次数为 \(\sum_{k=i+1}^j \max(0, b_k - i)\)，可以写出 DP \(f_{i, k} = \min_{1 \le j < i} f_{j, k - 1} + \sum_{t = i + 1}^j \max(0, b_t - i)\)。

发现贡献函数 \(w(j, i) = \sum_{t = i + 1}^j \max(0, b_t - i)\) 满足四边形不等式，那么答案关于 \(k\) 是凸的，具体可以看 决策单调性与四边形不等式学习笔记。于是我们可以直接 wqs 二分把第二维去掉。

然后考虑如何快速计算内层 DP，由于 \(b_k\) 具有单调性，我们可以设 \(p_i\) 为最小的 \(k\) 满足 \(b_k \ge i\)，那么就可以把 \(\max\) 拆掉了，发现是一个斜率优化的形式，直接做即可。不过还有一点，就是对于 \(p_j > i\) 的 \(j\) 这样计算贡献可能会算错（好像其实也不会影响，比较神秘），但是发现如果 \(b_i < j\) 那么你从 \(b_i\) 转移来一定是比它优的，所以这些地方可以直接不转移。

ABC327G Many Good Tuple Problems

我为啥上来就枚举左右部点的数量，我恼了，赛后十分钟过了。虽然我也没打吧。

考虑设 \(f_{n, m}\) 为 \(n\) 个点 \(m\) 条边的连通二分图方案数，发现这玩意不咋好做，发现任意图黑白染色的方案数是容易求的，即 \(\sum_{i=0}^n \binom{n}{i} (i(n-i))^m\)，假如设 \(f_{n,m}\) 的二元 EGF 为 \(F(x, y)\)，那么考虑到每一个连通块有两种染色方案，于是任意图黑白染色的方案数实际上等于 \([\frac{x^n}{n!} \frac{y^m}{m!}] e^{2F(x,y)}\)，那么有 \(e^{2F(x,y)} = \sum_{i \ge 0} \sum_{j \ge 0} \frac{x^i}{i!} \frac{y^j}{j!}\sum_{k=0}^i \binom{i}{k} (k(i-k))^j = \sum_{i \ge 0} \frac{x^i}{i!} \sum_{k=0}^i \binom{i}{k} \sum_{j \ge 0} \frac{(k(i-k)y)^j}{j!} = \sum_{i \ge 0} \frac{x^i}{i!} \sum_{k=0}^i \binom{i}{k} e^{k(i-k)y}\)，而我们要计算的答案实际上就是 \([\frac{x^n}{n!} \frac{y^m}{m!}] e^{F(x, y)}\)，于是令 \(G(x, y) = e^{2F(x, y)}\)，我们只需要计算 \([\frac{x^n}{n!} \frac{y^m}{m!}] \sqrt{G(x, y)}\) 即可。

发现 \(G(x, y)\) 可以表示成 \(x, e^y\) 的多项式，我们把 \(e^y\) 先换成 \(z\)，那么就可以暴力计算出 \(G(x,z)\) 的前 \(O(n^3)\) 项，然后开根可以 \(O(n^2)\) 开，具体利用 \(\sum_{i=0}^n f_i f_{n-i} = g_n\) 就可以直接递推计算了，那么需要循环 \(O(n^2)\) 次，每次计算长度为 \(O(n^2)\) 的卷积，那么此时我们就要计算 \([\frac{y^m}{m!}] \sum_{i=0}^{n^2} g_i e^{iy}\)，直接算就行了，总复杂度 \(O(n^4 \log n)\)。注意最后要乘 \(2^m\)，因为边可以随便定向。

2023.11.5

无模拟赛，所以今日摆大烂。

CF1237F Balanced Domino Placements

考虑枚举 \(a,b\) 表示有 \(a\) 个竖着放，\(b\) 个横着放，直接 DP 看起来不好 DP，我们可以先计算出行选 \(a\) 个长度为 \(2\)，\(b\) 个长度为 \(1\) 的段，和列选 \(b\) 个长度为 \(2\)，\(a\) 个长度为 \(1\) 的段的方案数，然后再乘一个 \(a!b!\) 就是总方案了，那么我们就变成了一维的问题。直接 DP 是 \(O(n^3)\) 的，注意到只有长为 \(2\) 的会被一开始的划分限制，那么我们先 DP 长为 \(2\) 的，然后计算时组合数选一下长为 \(1\) 的就行了，复杂度 \(O(n^2)\)。