AGC061 题解

标签：终点 题解 mask cdots AGC061 id dp 逆序

This is just sad. Wait, no, not just sad. Sad and enraging. Great job! -- Um_nik

A. Long Shuffle (1600)

打表容易发现当 \(n\) 为偶数时，对于所有 \(k \in [1,n/2]\)，\((A_{2k-1},A_{2k})=(2k-1,2k)\) 或 \((A_{2k-1},A_{2k})=(2k,2k-1)\)。

进一步打表发现当且仅当 \((k-1) \ \text{And} \ (n/2-1)=(k-1)\) 时取后者，否则取前者。

以上结论容易归纳验证。

于是当 \(n\) 为偶数时直接通过结论得到答案，当 \(n\) 为奇数时做两遍 \(n-1\) 即可。时间复杂度 \(O(T)\)。

Code

B. Summation By Construction (3400)

你这 B 怎么铜牌啊

我怎么把铜牌题过了啊

对 \(n\) 的奇偶性进行讨论。

Part 1 \(n\) 为奇数

考虑每个点作为链头或链尾的次数奇偶性，则左侧的点均为偶，右侧的点均为奇。猜想存在一种构造方案使得所有链均从右侧 \(1\) 号点出发，到右侧的其它每个点结束。

先删去右侧的 \(1\) 号点，变为所有链从左侧的每个点出发，到右边的每个点结束。

容易构造出以下方案：

5 5 3 3 1
4 5 5 3 3
4 4 5 5 3
2 4 4 5 5
2 3 4 4 5

再考虑右侧 \(1\) 号点的连接方式，显然奇数颜色连链尾，偶数颜色连链首即可：

5 5 3 3 1 1
4 5 5 3 3 4
4 4 5 5 3 3
2 4 4 5 5 2
2 3 4 4 5 5

于是 \(n\) 为奇数的情况得到解决。

Part 2 \(n\) 为偶数

由样例可知 \(n\) 为 \(2\) 时无解，但是事实上 \(n\) 为大于 \(2\) 的偶数时都有解，可以手玩出 \(n=4\) 的解：

4 4 3 2 3
1 4 4 2 2
3 3 4 4 2
1 3 3 4 4

仿照它来拓展，将最多的颜色放在中间，右上角每隔两个放一种颜色，这样会留出来一些空：

6 6 ? 4 ? 2 ?
? 6 6 4 4 2 2
? ? 6 6 4 4 2
? ? ? 6 6 4 4
? ? ? ? 6 6 4
? ? ? ? ? 6 6

左下角也每隔两个放一种颜色，并将链尾插到右上角的空里：

6 6 3 4 5 2 ?
5 6 6 4 4 2 2
5 5 6 6 4 4 2
3 5 5 6 6 4 4
3 3 5 5 6 6 4
? 3 3 5 5 6 6

最后两个未填的位置分别在左下角和右上角。将次多的颜色的链首移到链尾，再填上颜色 \(1\) 即可：

6 6 3 4 5 2 5
1 6 6 4 4 2 2
5 5 6 6 4 4 2
3 5 5 6 6 4 4
3 3 5 5 6 6 4
1 3 3 5 5 6 6

这样 \(n \geq 4\) 的情况都构造出了解，于是 \(n\) 为偶数的情况得到解决。

总时间复杂度 \(O(Tn^2)\)。

Code

C. First Come First Serve (2700)

切了 B 不会 C，哈哈

我场上没看到 \(A,B\) 递增，于是：

---

结论：对于每一个合法排列 \(P\)，存在唯一的长为 \(n\) 的序列 \(i_1,i_2,\cdots,i_n\) 使得 \(\forall t, A_{P_t}=i_t \vee (B_{P_t}=i_t \wedge i_{t-1}>A_{P_t})\)。

证明

先证明存在性：由于 $P$ 合法，先选出序列 $i'_1,\cdots,i_n$ 满足前两个条件 $\forall t, A_{P_t}=i_t \vee B_{P_t}=i_t$；再对不满足第三个条件的 $t$ 进行调整，每次调整 $\sum i_t$ 严格变小，故有限次调整后得到合法序列。

再证明唯一性：设序列 \(i_1,\cdots,i_n\) 和 \(j_1,j_2,\cdots,j_n\) 均合法。求出两个序列的最长公共前缀长度 \(l(l<n)\)，则由于 \(i_{l+1} \neq j_{l+1}\)，有 \(A_{P_{l+1}}=i_{l+1},B_{P_{l+1}}=j_{l+1}\)，那么 \(i_l=j_l < j_{l+1}\)，于是 \(j_{l+1}\) 不满足第三个条件，矛盾，故唯一性得证。

综上，证毕。

那么现在每个人有两种选择：

• 选择 \(A_i\)。

• 选择 \(B_i\)，要求 \([A_i,B_i)\) 内有数被选择。

对第二种选择容斥，每个人有三种选择：

• 选择 \(A_i\)，容斥系数为 \(1\)。

• 选择 \(B_i\)，容斥系数为 \(1\)。

• 选择 \(B_i\)，要求 \([A_i,B_i)\) 内无数被选择，容斥系数为 \(-1\)。

由于题目保证 \(A,B\) 均递增，考虑朴素 DP，设 \(dp_i\) 表示考虑前 \(i\) 个人，第 \(i\) 个人选择第三种选择的方案数。转移枚举上一个选择第三种选择的人 \(j\)，可以计算出 \((j,i)\) 的人选择前两种选择的方案数。

DP 可以前缀和优化，总时间复杂度 \(O(n)\)。

Code

D. Almost Multiplication Table (3600)

问 \(\max\) 的 \(\min\)，首先二分答案 \(K\)。设答案的上界 \(mx=\max\{A_{i,j},n^2+m^2\}\)。

现在问题变为构造 \(1 \leq x_1 < \cdots x_n\)，\(1 \leq y_1 < \cdots y_m\) 使得 \(\forall i,j,x_iy_j \in [A_{i,j}-K,A_{i,j}+K]\)。

一个很神奇的套路：调整法。考虑令 \(x_i\) 始终作为答案的下界，\(y_i\) 始终作为答案的上界。初始设 \(x_i=i,y_i=mx+K+i\)。不断执行以下操作：

• 顺序枚举每个 \(i\)，令 \(x_i \leftarrow \max\{x_i,x_{i-1}+1\}\)。检查每个 \(j\)，若存在 \(x_i y_j < A_{i,j}-K\)，令 \(x_i \leftarrow \lceil \dfrac{A_{i,j}-K}{y_j} \rceil\)。

• 倒序枚举每个 \(j\)，令 \(y_j \leftarrow \min\{y_j,y_{j+1}-1\}\)。检查每个 \(i\)，若存在 \(x_i y_j > A_{i,j}+K\)，令 \(y_j \leftarrow \lfloor \dfrac{A_{i,j}+K}{y_j} \rfloor\)。

那么每经过两轮，\(x_n\) 严格增加，\(y_m\) 严格减少，于是一定能找到解或发现无解。然而值域过大，时间复杂度无法接受。

考虑枚举 \(x_n,y_m\) 间的大小关系，不妨设 \(x_n \leq y_m\)（\(x_n > y_m\) 的情况可以交换 \(n,m\)）。那么在每一轮第一种操作后 \(x_n y_m \leq mx+K\)，于是 \(x_n \leq \sqrt{mx+K}\)，这意味着在 \(O(\sqrt{mx})\) 轮内必然能结束操作。

总时间复杂度 \(O(nm \sqrt{mx} \log mx)\)。

Code

E. Increment or XOR (3900)

考虑逐位处理。假设只考虑第 \(0,1,\cdots,k\) 位，关注整个过程中第 \(k-1\) 位是否向第 \(k\) 位进位：

• 第 \(k-1\) 位没有向第 \(k\) 位进位，那么只需要知道每种操作被使用次数的奇偶性就可以得知第 \(k\) 位的值。

• 第 \(k-1\) 位没有向第 \(k\) 位进位，那么一定存在一个时刻（即进位后的一瞬间）使得后 \(k\) 位均为 \(0\)。

设 \(dp_{k,id1,id2,mask}\) 表示只考虑第 \(0,1,\cdots,k-1\) 位，某个状态下代价最小值，其中 \(id_1\) 表示初始状态（为 \(0\) 表示 \(S\)，为 \(1\) 表示 \(0\)），\(id_2\) 表示终止状态（为 \(0\) 表示 \(T\) 且要求整个过程中不向第 \(k\) 位进位，为 \(1\) 表示 \(0\) 且仅在最后一次操作中进位），\(mask\) 表示每种操作被使用次数的奇偶性。

由 \(k\) 转移到 \(k+1\)，转移同样有两种：

• 若不进位，则若第 \(k\) 位匹配就有 \(dp_{k,id_1,id_2,mask} \rightarrow dp_{k+1,id_1,id_2,mask}\)。

• 若进位，则整个过程一定形如 \(S \rightarrow 100 \cdots 0 \rightarrow \cdots \rightarrow 100 \cdots 0 \rightarrow T\)。有转移 \(dp_{k,id1,1,mask_1}+dp_{k,1,1,mask_2}+\cdots+dp_{k,1,1,mask_{t-1}}+dp_{k,1,id_2,mask_t} \rightarrow dp_{k+1,id_1,id_2,\oplus mask_i}\)。注意每一步均要维护第 \(k\) 位匹配。

第二种转移可以使用类似 Dijkstra 算法的方式，当然不需要优先队列优化，每一次暴力找出最小值转移即可。

初始状态 \(dp_{0,id_1,0,mask}=\sum_{i \in mask} C_i\)，\(dp_{0,id_1,1,mask}=A+\sum_{i \in mask} C_i\)，这可以理解为 \(0.5\) 进位至 \(1\)（实际上就是直接加 \(1\)，为了方便转移理解为进位），这也是 \(A\) 唯一出现的地方。

总时间复杂度 \(O(4^n \log W)\)。

Code

F. Perfect Strings (4100)

首先是一个显然的转化：看做在 \(n \times m\) 的循环网格图上行走，\(0\) 为向右走，\(1\) 为向下走。于是问题转换为：

在 \(n \times m\) 的循环网格图上行走，每次只能向右或向下走，求从 \((1,1)\) 出发回到 \((1,1)\) 且除起终点不经过重复格子的回路数。

由于回路不定长，看起来没有什么特殊性质。

直接观察路径形态，容易发现整个回路是由若干条由左上边界到右下边界的连续路径组成的。考虑枚举这些路径的起终点，那么合法方案对应的起终点一定满足：

• 起点和终点数量相同，每个起点的对面都是终点，每个终点的对面都是起点。

• 第 \(1\) 行或第 \(1\) 列上必须存在起终点（因为必须从 \((1,1)\) 出发）。

• 记行上起终点数量为 \(r\)，列上起终点数量为 \(c\)，则 \(\gcd(r,c)=1\)（否则会形成多个回路）。

为了方便暂时先不考虑第二个条件。

同时若将所有起点及终点分别从右上至左下排序，则它们的连接方式必然是顺序一一对应的。

那么如果枚举了起终点，直接使用 LGV 引理计算不交路径组数即可。

然而无法枚举起终点，矩阵也难以维护，直接计算行不通。

考虑更改图的形态，将所有行列都考虑进来，但允许一些相对的行列同时不作为起终点。同时引入变元 \(x,y\) 作为边权以统计 \(r,c\)，如下图：

（图来自官方题解）

再使用 LGV 引理。但现在出现了一个问题：LGV 引理得到的结果中排列 \(\sigma(S)\) 的方案数会带一个 \((-1)^{inv(\sigma(S))}\)（\(inv(P)\) 表示逆序对数）的权值，对于同一个 \(x^{n-r} y^{m-c}\) 项这个值有可能不一样。

幸运的是，对于同一对 \((r,c)\) 逆序对数总是相同的。下面进行推导。

只考虑左上边界的点。称起点为特殊点，其它点为普通点。

首先特殊点间的逆序对数容易计算：行特殊点及列特殊点内部没有逆序对，而行特殊点及列特殊点间产生 \(rc\) 对逆序对。

同样普通点内部也没有逆序对。

考虑一个列特殊点 \(t\) 与普通点间的逆序对数。如果只有它一个列特殊点，那么普通点 \(t+1,\cdots,n+t\) 会与它产生逆序对。

进一步的，产生逆序对的普通点是一段区间。记 \(c[l,r]\) 表示标号为 \([l,r]\) 的点中特殊点的数量，则区间左端点是 \(t-c[1,t)\)，右端点是 \(n+t-c[1,t)-c[m+1,m+n]-1\)。

故该特殊点产生的逆序对数为 \(n-r\)。逆序对总数为 \((n-r)c+(m-c)r+rc=nm-(n-r)(m-c)\)。

于是这个问题得到解决。

还有一点小细节：第 \(1\) 行或第 \(1\) 列上必须存在起终点。显然这两个条件不可能同时满足，那么不妨设第一列上必须存在起终点，即不允许第一列的两个点同时不作为起终点，将对应边删去即可。

最后只需要计算下列矩阵的行列式：

暴力做法是对每个 \((x,y)\) 进行二元多项式插值，复杂度 \(O(nm (n+m)^3)\)，足以通过本题。

更优秀的做法是将 \(y\) 换元成 \(rx\)，对 \(r\) 进行插值。注意到将整个矩阵的每个元素除去 \(x\) 后即求关于 \(x^{-1}\) 的特征多项式，可以 \(O((n+m)^3)\) 解决。于是总复杂度 \(O(n(n+m)^3)\)。

事实上任何形如 \(det(A+Bx+Cy)\) 的问题都可以在 \(O(n^4)\) 内得到解决：只需要对 \(x\) 进行插值，跑 \(det(A+Bz)\) 即可。

代码只实现了 \(O(nm(n+m)^3)\) 做法。

Code

标签：终点,题解,mask,cdots,AGC061,id,dp,逆序
From： https://www.cnblogs.com/Appleblue17/p/17146640.html