对于每一行的 $-1$，显然只会填一种数字，因此可以得出一种比较朴素的 DP。设 $f_{i,j}$ 表示考虑前 $i$ 行，第 $i$ 行的 $-1$ 变为 $j$ 时的最大值，再设 $d_{i,j}$ 表示第 $i$ 行数字 $j$ 的个数，则可...

Weighted Tic-Tac-Toe 用二进制表示每一格的情况，然后必胜态和必败态需要相互转换。 Remove Pairs 直接状压，时间复杂度 $O(2^nn^2)$。 Exchange Game $dp_{f,st}$ 表示某一方...

定义：一棵有根树形成的任一排列 $p$，若 $i$ 是 $j$ 的父亲，排列 $p$ 均满足 $i$ 在 $j$ 之前。更加形式化的，$\forall 1 \le i < j \le n$，$p_j$ 均不是 $p_i$ 的父亲。 结论：设...

母题—逆序对与期望 求长度为 $n$ 的排列的期望的逆序对个数。 对于每一对数，是否成为逆序对的概率显然为 $\frac{1}{2}$，那么就有： E(x) = E(\sum\limits_{i,j\mid i < j}[a_i > a_j])...

$\gcd (x,y)$ 求两个数 $x,y(x > y)$ 的最大公因数，辗转相除法即可。 1int gcd (int x,int y){return !y ? x : gcd (y,x % y);} $\rm l...

将行和列分开考虑。 在每组询问 $(x_1,y_1,x_2,y_2)$ 中： 对于每一行，相邻的两个数的下标差为 $1$。 对于每一列，相邻的两个数的下标差为 $y_2 - y_1 + 1$。 不难想到对行和列分别做 $i \times a_...

题意： 初始时 $a = [0,1]$，每次更新将 $a$ 逆序对的数量 $k$ 插入其中，求最终长度为 $n$ 的序列的数量。 以下均设当前的序列逆序对的数量为 $k$。 首先需要通过观察得出一个性质，当序列第一次出现 $k > 1$ 的时候...

由数据范围不难想到按位考虑，所以我们尽量把每次询问凑成 $2$ 的幂次相关的数。 在二进制条件下，设最低位为第 $0$ 位。目前要猜测第 $i$ 位的值，设 $t$ 表示前 $i - 1$ 位所贡献的值。令 $a < b$，则有（加粗表示第 $...

从给定集合中选数并构造序列 $\{a_i\}$，需要满足 $a_{\gcd (i,j)} \neq \gcd(a_i,a_j) \mid \forall 1 \le i < j \le n$ 并且构造出的序列字典序最大。 不妨从反面分析，考虑满...

给定 $x,m$，求有多少 $y$ 满足 $y \in [1,m]$ 使得 $x \oplus y$ 可以被 $x$ 或 $y$ 整除。 设 $p = x \oplus y$，分三种情况讨论： $x | p$。设 $p = kx$，则 $y = x...