2A
题意：
1A
题意：给定 \(n \times n\) 种物品，\((i, j)\) 有 \(a_{i, j}\) 个，权值为 \(b_{i, j}\)，两个物品等价当且仅当 \(i\) 相等或 \(j\) 相等。
初始有一个空（可重）集 \(S\)，每次等概率从剩余物品中选一个 \(x\) 出来。
如果 \(S\) 中没有和 \(x\) 等价的物品，那么 \(x\) 加入 \(S\)；否则把所有和 \(x\) 等价的物品拿出来放回去。
每轮操作后会把 \(\sum_{x \in S} b_x\) 累计进积分，求 \(k\) 轮操作后积分的期望值。\(2 \le n \le 4,\ 1 \le k \le 10^9\)。
注意到 \(S\) 中元素一定互不相同，这提示我们符合条件的局面实际很少，\(n = 4\) 的时候合法局面只有 \(209\)。
每轮的贡献只与 \(S\) 有关，因此只要计算出第 \(i\) 轮操作后局面为 \(S\) 的概率 \(p(i, S)\) 即可。
矩阵快速幂加速转移，同时维护 \(E_{i - 1}\) 表示上一轮的期望权值，时间复杂度 \(O(N^3\log k),\ N = 210\)。
B
题意：\(2n\) 个 \(k\) 维空间上的点，定义 \(\text{dist}(p_i, p_j)\) 为两点的曼哈顿距离。
\(A, B\) 两人进行游戏，\(A\) 先手。每人每轮选一个点，设 \(A\) 选出集合为 \(S_A\)，\(B\) 为 \(S_B\)。
设 \(\sum_{i < j\in S_a} \text{dist}(p_i, p_j) - \sum_{i < j \in S_b} \text{dist}(p_i, p_j)\)，\(A\) 想要最大化这个权值，\(B\) 想要最小化。求两人都在最优决策下的最终权值。
数据范围：\(1 \le n, k \le 10^5,\ n \times k \le 10^5\)。
\[\begin{aligned} & \sum_{i < j\in S_a} \text{dist}(p_i, p_j) - \sum_{i < j \in S_b} \text{dist}(p_i, p_j)\\ \\ =& \bigg(\sum_{i < j\in S_a} \text{dist}(p_i, p_j) + \sum_{i < j\in S_b} \text{dist}(p_i, p_j) + \sum_{i \in S_a, j\in S_b} \text{dist}(p_i, p_j) \bigg) - \bigg(\sum_{i < j \in S_b} \text{dist}(p_i, p_j) + \sum_{i > j\in S_b} \text{dist}(p_i, p_j) + \sum_{i \in S_a, j\in S_b} \text{dist}(p_i, p_j)\bigg)\\ \\ =& \sum_{i, j \in U} \text{dist}(p_i, p_j) - \sum_{i \in U,\ j \in S_b} \text{dist}(p_i, p_j) \end{aligned} \]前一项是定值，因此每个人的决策就是取当前到所有点距离和最大的点。submission