日记

不是我中邪了啊 $10$ 分的暴力都能挂？

T1 # Link to T1

对于 $a_i$ 和 $p_i$ 的奇偶性不同的，我们先把 $a_i$ 加上 $1$。把 $s$ 减掉 $1$，表示方案需要在 $(s,t]$ 这段区间内。再把 $s$ 和 $t$ 都减掉 $\sum_{i = 1}^{n}a_i$，表示先都取一个 $a_i$。这时如果 $s < 0$ 就把 $s$ 赋值成 $-1$，$t < 0$ 就无解直接结束。

而我们又发现剩下的一定是两个两个取的，于是我们可以把 $s \gets \lfloor \frac{s}{2} \rfloor,t \gets \lfloor \frac{t}{2} \rfloor$，再有 $c_i = \lfloor \frac{b_i - a_i}{2}\rfloor$（这个 $a_i$ 是和 $p_i$ 奇偶性相同的 $a_i$）。问题就变成了每个点都取不超过 $c_i$ 个数，使得总和在 $(s,t]$ 这个区间内的方案数。

我们可以求出总和小于等于 $s$ 的方案数 $calc(s)$ 和总和小于等于 $t$ 的方案数 $calc(t)$。那么最终的答案就是 $calc(t) - calc(s)$。

考虑如何求 $calc(x)$。我们可以容斥。枚举二进制状态 $s$，表示钦定 $s$ 集合内的点超限了。那么剩下的点就是 $x - \sum_{i \in s}(c_i + 1)$。而我们要把这么多数分给 $n + 1$（$n + 1$ 的原因是我们求的是小于等于的，不要的我们就扔给 $n + 1$）个点，使用插板法，总方案数就是 $\binom{n + x - \sum_{i \in s}(c_i + 1)}{n}$，乘上一个容斥系数然后相加就是了。

然后还有神秘非质模数，需要使用奇技淫巧组合数。

Sorting a Grid# Link to

考虑 $B,C$ 矩阵满足什么性质。设 $D_{i,j}$ 这个数的颜色是 $i$，那么 $C$ 的每一行颜色都必须一样，$B$ 的每一列必须包含所有 $n$ 个颜色。我们发现这就是 $m$ 个完美匹配。那么我们可以对于每个 $A_{i,j}$，建一条 $i \to col(A_{i,j})$，容量为 $1$ 的边，然后跑 $m$ 次 dinic 就是了，复杂度 $O(nm\sqrt{n})$。

Two Permutations# Link to

我们发现一个排列可以表示成许多个环，而我们需要构造的 $A,B$ 也是一个排列，所以如果 $A_i = P_i$，它就会挤掉 $A_{P_i}$ 的值，让它不能取到 $A_{P_i} = P_i$，而这样它又会挤掉下一个的值，以此往复，整个环都没有 $A_i = i$ 的了。于是我们得到一个结论：一个环要么整个都没有 $A_i = i$，要么整个都是 $A_i = i$。

我们对于一个 $P_i,Q_i$ 分类讨论，设 $P_i \in a_i$ 的环，$Q_i \in b_i$ 的环。（$a_i$ 和 $b_i$ 都只是环的编号）

1. $P_i = i,Q_i = i$
   必定造成 $1$ 的贡献
2. $P_i = i \land Q_i \ne i$
   在 $b_i$ 被拆开时造成 $1$ 的贡献。
3. $P_i \ne i \land Q_i = i$
   在 $a_i$ 被拆开时造成 $1$ 的贡献
4. $P_i = Q_i \ne i$
   在 $a_i$ 和 $b_i$ 同拆和同不拆时造成 $1$ 的贡献
5. $P_i \ne i \land Q_i \ne i \land P_i \ne Q_i$
   在 $a_i$ 和 $b_i$ 同拆时造成 $1$ 的贡献。

于是我们就可以开始网络流求最小割。

1. $tot - 1$。
2. $s \to b_i$，容量为 $1$。
3. $a_i \to t$，容量为 $1$。
4. $a_i \leftrightarrow b_i$，容量为 $1$。
5. $a_i \to b_i$，容量为 $1$。

最后的答案就是 $tot - flow$。

后日谈 # Link to 后日谈

不该如此。