M-SOLUTIONS Programming Contest 2021

E

Rook Path
题目大意
给定一个 n×5n \times 5 的棋盘，有一个车，每一次必须移动，能够移动到当前所在的行的同一行任意一个位置
或者是当前所在列同一列的任意一个位置，起始时候在 (x1,y1)(x_1, y_1)，移动 kk 步，问 kk 步后在 (x2,y2)(x_2, y_2)
有多少种可能性

不难想到是 dpdp，用移动的步数作为 dpdp 的阶段，不难列出状态转移方程如下
f(k,x,y)f(k, x, y) 表示当前第 kk 步，位于 (x,y)(x, y) 的方案数，则
f(k,x,y)=∑x′≠xf(k−1,x′,y)+∑y′≠yf(k−1,x,y′)\displaystyle f(k, x, y) = \sum_{x' \neq x} f(k-1, x', y) + \sum_{y' \neq y} f(k-1, x, y')

考虑优化，因为最后只与 x′=x?y′=y?x' = x? \quad y' = y? 有关，可以考虑状态压缩
用 00 表示 x′=xx' = x，11 表示 x′≠xx' \neq x，同样 00 表示 y′=yy' = y，11 表示 y′≠yy' \neq y
这样不难列出如下状态转移方程

dp(k,0,0)=dp(k−1,1,0)+dp(k−1,0,1)dp(k, 0, 0) = dp(k-1, 1, 0) + dp(k-1, 0, 1)
说明，此时 k−1→kk-1 \to k 过程中只能有一种移动方式，即同行或同列移动

dp(k,1,0)=dp(k−1,0,0)⋅(n−1)+dp(k−1,1,0)⋅(n−2)+dp(k−1,1,1)dp(k,1, 0) = dp(k-1, 0, 0) \cdot (n-1) + dp(k-1, 1, 0) \cdot (n-2) + dp(k-1, 1, 1)
此时 kk 阶段所在的列 y′y' 是确定的，k−1→kk-1 \to k 有两种情况，即在当前列移动，或者从其他列移动到当前列
从其他列移动到当前列，只有一种平移方式，即直接移动到 y′y' 列，当前列移动呢？考虑 k−1k-1 阶段能够选择的行有多少种？

dp(k,0,1)=dp(k−1,0,0)⋅(m−1)+dp(k−1,0,1)⋅(m−2)+dp(k−1,1,1)dp(k, 0, 1) = dp(k-1, 0, 0) \cdot (m-1) + dp(k-1, 0, 1) \cdot (m-2) + dp(k-1, 1, 1)
和上一种情况完全对称

dp(k,1,1)=dp(k−1,1,0)⋅(m−1)+dp(k−1,0,1)⋅(n−1)+dp(k−1,1,1)⋅(n−2+m−2)dp(k, 1, 1) = dp(k-1, 1, 0)\cdot (m-1) + dp(k-1, 0, 1) \cdot (n-1) + dp(k-1, 1, 1) \cdot (n-2 + m-2)
第 k−1k-1 阶段可能和 kk 阶段，同行不同列，从 (m−1)(m-1) 列中任选一列作为状态，不同行同列，从 (n−1)(n-1) 行任选作为状态
还有就是不同行，不同列，此时能选择行移动或者列移动，有 n−2+m−2n-2 + m-2 种选择

根据这 44 种情况 dpdp 即可，一开始时候 dp(0,0,0)=1dp(0, 0, 0) = 1，dpdp 的终点是什么呢？
考虑 x2=x1?x_2 = x_1? 或者是 y2=y1?y_2 = y_1? 判断终点状态是 (0,0),(0,1),(1,0),(1,1)(0, 0), (0, 1), (1, 0), (1, 1) 哪一种
比如 xx 坐标对应的状态是 11，那么终点和起点行不同，x2x_2 是这些不同状态中的任意一种，答案是 dp(1,⋯ )/(n−1)dp(1,\cdots) / (n-1)
如果相同呢？那么行可以选择的情况只有 11 种，dp(0,⋯ )/1dp(0, \cdots) / 1，yy 情况同理
用向量 vx={1,n−1},vy={1,m−1}\bm{vx} = \{1, n-1\}, \bm{vy} = \{1, m-1\}，对于最后的状态 dp(i,j)dp(i, j)
返回 dp(i,j)/vx(i)/vy(j)dp(i, j) / \bm{vx}(i) / \bm{vy}(j) 即可，其中 i←(x2=?x1)i \leftarrow (x_2 =? x_1)

F

Simple Operations on Sequence
题目大意
给定大小为 nn 的数组 A,BA, B，一次操作可以有如下两种
任意选择 AiA_i，让其 +1+1 或者 −1-1，产生 XX 代价，或者是任意交换 AA 中的两个元素，产生 YY 代价
问需要最少的代价，使得 A,BA, B 相等

算法分析
首先对于 n⩽18n \leqslant 18，不难想到是状态压缩，转移方程大致如下
假设当前处理第 ii 个数，其中前面 i−1i-1 个数都相等，即 j∈[0⋯i−1]j \in [0\cdots i-1] 均有 Aj=BjA_j = B_j
此时加入 ii，令 Ai=BiA_i = B_i，有状态转移
dp(s∣(1≪i))=min⁡(dp(s)+cost(Ai=Bi))dp(s \mid (1\ll i)) = \min \left(dp(s) + \textbf{cost}(A_i = B_i)\right)
难点在于 cost(Ai=Bi)\textbf{cost}(A_i = B_i) 怎么计算

注意代价有两部分组成

  • (A1,A2,⋯ ,An)→(Ap1,Ap2,⋯ ,Apn)(A_1, A_2, \cdots, A_n) \to (A_{p_1}, A_{p_2},\cdots, A_{p_n})，这里转换的代价，实际上是排列
    P=(p1,p2,⋯pn)P=(p_1, p_2, \cdots p_n) 逆序对的数目 inv(P)\textbf{inv}(P)，这部分的代价为 inv(P)⋅Y\textbf{inv}(P) \cdot Y
  • 还有一部分代价就是 ∑i=1n∣Api−Bi∣\displaystyle\sum_{i = 1}^{n} |A_{p_i} - B_i|

算法设计
这里让 BB 数组不动，改变 AA 数组，用一个状态 ss 来表示，其中 ss 中为 11 的位 ii 表示
B(i)=A(pi)B(i) = A(p_i)，即已经确定了 BiB_i 这一位和 AA 中对应的位 ApiA_{p_i} 相等
状态转移是 dp({00⋯0})→dp({11⋯1})dp(\{00\cdots 0\}) \to dp(\{11\cdots 1\})

考虑某个状态 ss，尝试加入不在 ss 中的元素 xx，dp(s)⟶dp(s∪{x})dp(s) \longrightarrow dp(s \cup \{x\})

  • 首先计算 ss 中有多少个 11，不妨设有 jj 个 11，说明已经确定了 (B1,B2,⋯ ,Bj)(B_1, B_2, \cdots, B_j)
    当前正在确定 Bj+1B_{j+1}，将 xx 加入 ss 集合的代价是 ∣A(x)−B(j+1)∣⋅X|A(x)-B(j+1)| \cdot X
  • 考虑加入 xx 过程，AA 的下标 {{p1,p2,⋯ ,pj},pj+1}←{{p1,p2,⋯ ,pj},x}\{\{p_1, p_2, \cdots, p_{j}\}, p_{j+1}\} \leftarrow \{\{p_1, p_2, \cdots, p_{j}\}, x\}
    那么代价要加上 A(1,2,⋯j)→A(p1,p2,⋯pj)A(1, 2, \cdots j) \to A(p_1, p_2, \cdots p_j)，实际上是计算 inv(P[1→j])\text{inv}(P[1\to j])
    即前 jj 个数逆序对的个数，实际上，因为 PP 是一个排列，x∈{1⋯n}x \in \{1\cdots n\}，需要看一下
    ss 中 下标 <x< x 的位，是不是都在 ss 中
    如果发现 ss 中的 pp 位为 00，并且 p<xp < x，那么逆序对的个数就 +1+1，最后算出此时的逆序对 inv(s,x)\text{inv}(s, x)
    代价要加上 inv(s,x)⋅Y\text{inv}(s, x) \cdot Y
  • 状态转移方程如下，dp(s∪{x})⟵min⁡x∉s(dp(s)+inv(s,x)⋅Y+∣Ax−Bj+1∣⋅X)dp(s\cup \{x\}) \longleftarrow \displaystyle\min_{x \notin s}\left(dp(s) + \text{inv}(s, x)\cdot Y + |A_x - B_{j+1}|\cdot X\right)
    其中，jj 为 ss 中 11 的个数，表示当前已经确定了 B[1⋯j]B[1\cdots j] 中所有元素，正在安排 Bj+1B_{j+1}

结论
如何计算一个排列 (1,2,⋯ ,i)→(p1,p2⋯ ,x)(1, 2, \cdots, i) \to (p_1, p_2 \cdots, x) 的逆序对个数？
实际上遍历整个排列，如果比 xx 小的数都在 xx 前面，那么逆序对很显然是 00
逆序对的个数，实际上要统计 xx 之前（如果用一个集合维护的话，就是统计集合中）
有多少个数 <x< x 并且不在集合中

G

Modulo Shortest Path
题目大意，给定 nn 个点的完全图，给定 a[1⋯n],b[1⋯n]a[1\cdots n], b[1\cdots n]，任意 i,j,i≠ji, j, i \neq j
有 (i→j)(i\to j) 的有向边，权值为 (ai+bj) mod M(a_i + b_j) \bmod M，问从 1→n1 \to n 的最短路径

如果直接在原图上跑 dijkstra\text{dijkstra}，因为图的规模是 O(n2)O(n^2)，必然会超时
注意到任意两点 i,ji, j 的权值总是在 MM 的剩余系中，考虑剩余系的值 {0‾,1‾,⋯ ,M−1‾}\{\overline{0}, \overline{1}, \cdots, \overline{M-1}\}
这样实际上只需要考虑 MM 个点即可
G

算法设计
可以考虑拆边，将长度为 MM 的边，依次拆成 0→1→⋯→M−1→00 \to 1 \to \cdots \to M-1 \to 0 的环，两点间的长度分别为 11
(i,j)=(Ai+Bj) mod M(i, j) = (A_i + B_j) \bmod M，应该对应一张图 G′G'，其中从 ii 进入环上的某个点 p1‾\overline{p_1}
然后从 pr‾\overline{p_r} 处离开环，进入 jj

(Ai+Bj) mod M=r(A_i + B_j) \bmod M = r，可以推出 Bj≡(−Ai)+r ( mod M)B_j \equiv (-A_i) + r \ (\bmod M)
也就是说，如果令 p1‾=(−Ai mod M)\overline{p_1} = (-A_i \bmod M)，令边 (i,p1‾)(i, \overline{p_1}) 的权值为 00
又因为 Bj=(−Ai‾+r)B_j = (\overline{-A_i} + r)，也就是说 BjB_j 是在环上距离 −Ai‾\overline{-A_i} 恰为 rr 的点
令 pr‾←(Bj mod M)\overline{p_r} \leftarrow (B_j \bmod M)，并且令 (pr‾,j)(\overline{p_r}, j) 的权值为 00
原问题和图 G′G' 恰好一一对应

再观察发现，我们根本用不到 MM 个点，实际上，只有 −Ai‾( mod M)\overline{-A_i}(\bmod M) 和 Bi‾( mod M)\overline{B_i}(\bmod M)
这些点是有意义的，离散化后将其放入集合 vv 中，按剩余系的值排序，然后按从小到大的顺序依次连边
离散化之后对应的原来剩余系的值为 rm(vi)\text{rm}(v_i)
新图中令 (vk,vk+1)(v_k, v_{k+1}) 的权值为 (rm[vk+1]−rm[vk])(\textbf{rm}[v_{k+1}] - \textbf{rm}[v_k])
这样只有 O(2n)O(2n) 个点，可以直接 dijkstra\text{dijkstra}
另外注意图中剩余系是有环的，如果遍历到 vmv_{m} 最后一个元素，（假设 vv 中最后一个元素是 vmv_m）
需要在 (vm,v0)(v_{m}, v_0) 之间连边，权值为 (M+rm[v0]−rm[vm]) mod M(M + \textbf{rm}[v_0] - \textbf{rm}[v_{m}]) \bmod M

算法实现

  • 建一张新图 GG，用 get(x,type)\text{get}(x, type) 表示点 xx 对应在新图中点的编号，其中 type=0type = 0 表示原图中的点
    type=1type = 1 表示剩余系
  • 对每一个 aia_i，在 i⟶(−ai mod M)‾i\longrightarrow \overline{(-a_i \bmod M)} 建一条有向边，权值为 00
    同理对每一个 bib_i 在 bi mod M‾⟶i\overline{b_i \bmod M} \longrightarrow i 建一条有向边，权值为 00
    将 (−ai mod M)‾\overline{(-a_i \bmod M)} 和 bi mod M‾\overline{b_i \bmod M} 加入集合 vv 中并排序
    然后对集合 vv 中的元素按前面描述的方式，加入有向边
  • 对新图从 get(1,0)→get(n,0)\text{get}(1, 0) \to \text{get}(n, 0) 跑 dijkstra\text{dijkstra} 即可