A. 01 Matrix

令 $\{B_{ij}\}$ 为 $\{A_{ij}\}$ 的二维前缀和，即 $B_{ij}=\bigoplus_{x=1}^i\bigoplus_{y=1}^j A_{xy}$。容易发现 $A$ 和 $B$ 一一对应。

限制条件可以转化为 $B_{xy}=1$ 和 $B_{xM}\oplus B_{Ny}\bigoplus B_{NM}=0$。注意因为 $x,y< N$，两类限制互不相交。对于第一类限制，我们只需要数有多少对不同的 $(x,y)$。对于第二类限制，我们可以枚举 $B_{NM}$ 后，转化为在 $(x,M)$ 和 $(N,y)$ 之间连一条边权为 $B_{NM}$ 的边，然后判断是否为二分图，如果是则答案取决于连通块数量。时间复杂度 $O(K\log K)$。

B. Birds-of-Paradise' Card Game

观察：一定存在最优解满足能分成若干形如 $w^is^j$ 的段，且段之间互不影响。

证明：如果段之间有影响，一定形如 wsws。假设 $S[i:i+3]={\tt wsws}$，考虑替换成 wwss 什么时候不优，这样的替换只会使得 $S_{i+5}={\tt s}$ 时的贡献减少，且根据贡献的凸性，只有在 $S[i+2:i+4]$ 全都是 w 的时候答案才可能变小，而这是不可能的。因此任意的解都可以通过有限次上述的替换变成满足条件的解，且答案不会变小。

现在问题变成了把形如 $w^is^j$（$i,j\le 3$）的段拿去做背包，使得价值尽可能大。设这样的段的贡献为 $f(i,j)$，那么考虑点集 $S=\left\{\left(\frac{i}{i+j},\frac{f(i,j)}{i+j}\right)\right\}$，当 $W$ 和 $S$ 足够大时可以近似看作选择 $S$ 中的点的一个线性组合，使得横坐标为 $\frac{W}{W+S}$，且纵坐标尽可能大。此时一定只会选择 $S$ 的上凸包的一条边的两个端点。现在要求的是精确解，也可以发现如果选了太多除这两个点以外的点，都可以替换成这两个点使得答案不劣。枚举选择的其他点的 w 和 s 数量的总和，暴力预处理小范围背包，就可以 $O(1)$ 回答。

C. Don't be Clockwise

从凸包上的一条边开始，每次沿当前点逆时针旋转直到碰到第一个点，然后从这个点继续，这样每次都能保证剩下的所有点都在当前直线左侧，因此都是逆时针方向。时间复杂度 $O(N^2)$。

D. Except Ai

每次贪心选最长的一段前缀满足至少有一个数没有出现即可，因为这个段的长度至少是 $X-1$，因此可以直接用数组记录出现过的数。时间复杂度 $O(N)$。

E. Find ''rururutata''

只要找到每个位置往前最短的形如 $rrr$ 的后缀，和往后最短的形如 $tt$ 的前缀即可。可以用各种方式枚举 Runs 做到，例如后缀数组。

F. Increase Decrease

有解的必要条件是 $A_1=B_1=1$，$A_{i+1}\ge A_i$，$B_{i+1}\ge B_i$，$A_i\cdot B_i\ge i$，$(A_{i+1}-A_i)+(B_{i+1}-B_i)\le 1$。

设 $f_i$ 和 $g_i$ 分别为以 $i$ 结尾的 LIS 和 LDS 长度，我们可以先为每个数分配 $f_i$ 和 $g_i$，满足所有 $(f_i,g_i)$ 互不相同，且每个前缀的 $(f_i,g_i)$ 形成了一个阶梯形，这在上述的限制下是一定能做到的。之后我们令第 $i$ 个数为 $f_i\cdot N-g_i$，容易证明这个序列满足 $f_i$ 和 $g_i$ 的条件，最后离散化成排列即可，时间复杂度 $O(N)$。

H. OR Preference

观察：如果先做 AND 再做 OR，一定不如先做 OR 再做 AND。证明只需枚举所有情况。

现在问题转化为把数组分成尽可能少的段，使得每一段的 OR 的 AND 等于 $0$。考虑 DP，令 $f(i,x)$ 表示把前 $i$ 个数分成若干段，当前的 AND 是 $x$ 时最少的段数。暴力转移是 $O(N^2V)$ 时间。

注意到转移是把 $x$ 和 $A_{i+1}\operatorname{or}\cdots\operatorname{or} A_{j}$ 取 AND，后者对于固定的 $i$ 只有 $\log V+1$ 段，对于每一段和给定的 $x$，转移相当于对于 $r,y$ 把所有满足 $i< j\le r$ 的 $f(j,y)$ 对 $f(i,x)+1$ 取较小值。这样的转移可以用一个数组 $g(x,v)$ 表示所有满足 $i< j\le g(x,v)$ 的 $f(j,x)$ 对 $v$ 取较小值。注意到如果有解，则答案不超过 $2\log V+1$，因为我们可以找到 $\log V$ 个数，把这些数单独分成一段。因此 $v$ 也只有 $O(\log V)$ 级别，从而我们可以在 $O(\log V)$ 的时间内得到一个位置的 DP 值 $f(i,x)$。总时间复杂度 $O(NV\log V)$。

要进一步优化，首先考虑我们可以认为 $f(i+1,x)\le f(i,x)+1$，这是因为我们可以把 $A_{i+1}$ 单独分成一段，虽然可能会使得 $x$ 的位数变小，但是我们认为 $x$ 保持不变不会使得答案变得更小。这样我们就可以 $O(1)$ 得到每个位置的 DP 值。其次，考虑 $A_{i+1}\operatorname{or}\cdots\operatorname{or} A_{j}$ 的 $\log V+1$ 段，我们按照从后往前的顺序处理，每一段是让每个 $x$ 转移到 $x\operatorname{and} y$，这里 $y$ 二进制中 $1$ 的个数不断减小，而对于 $y$ 二进制中等于 $0$ 的位，我们不需要知道 $x$ 对应的位是多少，因此可以直接每次压缩掉 DP 数组中减少的那一位，从而时间复杂度变为 $\sum_{i=0}^{\log V}O(2^i)=O(V)$。总时间复杂度 $O(NV)$。

一个更简单的做法是，发现固定 $j,x$ 之后，形如 $f(i,x)\to f(j,y)$ 的转移，只有 $i$ 这一维的后缀最小值有用，因为如果区间更长且答案更大，则一定不优。而我们可以假设对任意的 $j>i$ 都有 $f(j,x)\le f(i,x+1)$，原因和上面一致。所以事实上后缀最小值不超过两个，因此容易做到 $O(NV)$ 时间复杂度。

I. Penguin Flicker

令 $P'_i=P_i-i$，这样每次移动就是直接移到上一个或下一个企鹅的位置，而不是有 $1$ 的距离。容易发现这时答案一定可以表示为 $N+1$ 个间隔长度的线性组合加上一个常数。

令 $f(n,i)$ 表示剩余 $n$ 个企鹅时第 $i$ 段间隔（第 $i-1$ 和第 $i$ 个企鹅之间）的系数，讨论下一次操作，可以得到以下转移： $$ f(n,0)=\frac{1}{n}f(n-1,0)+\frac{1}{2n}+\frac{n-1}{n}f(n,0)\\ f(n,n)=\frac{1}{n}f(n-1,n-1)+\frac{1}{2n}+\frac{n-1}{n}f(n,n)\\ f(n,i)=\frac{1}{2n}f(n-1,i-1)+\frac{1}{2n}f(n-1,i)+\frac{1}{n}+\frac{1}{2n}f(n,i-1)+\frac{1}{2n}f(n,i+1)+\frac{n-2}{n}f(n,i) $$ 对于每个 $n$ 我们可以设 $f(n,1)$ 为未知数 $x$，将所有 $f(n,i)$ 表示为 $kx+b$ 的形式，然后解方程得到 $x$。

对于常数部分，令其为 $g(n)$，主要来源于当最左边或者最右边的企鹅掉落时，新的段的长度除了左右两段合并，还会额外加 $1$，因此可以得到： $$ g(n)=\frac{1}{n}g(n-1)+\frac{1}{2n}f(n-1,0)+\frac{1}{2n}f(n-1,n-1)+\frac{n-1}{n}g(n) $$ 总时间复杂度 $O(N^2+TN)$。

J. Set Sequence

令 $M=\sum_{i=1}^NA_i$。我们对每个 $c\le M$ 计算恰好 $c$ 个集合的序列数量，通过容斥空集可以得到 $$ \sum_{x=0}^c(-1)^{c-x}{c\choose x}\prod_{i=1}^N{x\choose A_i} $$ 对所有 $c$ 求和就是答案。

令 $f(x)=\prod_{i=1}^N {x\choose A_i}$，因为 $A_i< P$，通过 Lucas 定理可知 $f(x+P)=f(x)$，所以我们按照 $x\bmod P$ 分类，可以得到答案等于 $$ \sum_{x=0}^{P-1}\sum_{c=x}^{P-1}\sum_{iP+x\le jP+c\le M}(-1)^{(j-i)P+(c-x)}{j\choose i}{c\choose x } f(x) $$ 因为固定 $x,y,j$ 的时候，$i$ 的贡献是 $\sum_{i=0}^j(-1)^{j-i}{j\choose i}=[j=0]$，所以上述求和可以化简为 $$ \sum_{x=0}^{P-1}f(x)\sum_{c=x}^{P-1}(-1)^{c-x}{c\choose x} $$ 而事实上在 $\bmod P$ 意义下，有 $$ \begin{aligned} &\sum_{c=x}^{P-1}(-1)^{c-x}{c\choose x}\\ =&\sum_{i=0}^{P-1-x}(-1)^i{x+i\choose i}\\ =&\sum_{i=0}^{P-1-x}{-1-x\choose i}\\ =&\sum_{i=0}^{P-1-x}{P-1-x\choose i}\\ =&2^{P-1-x} \end{aligned} $$ 所以剩下的难点在于计算所有的 $f(x)$。

因为将组合数展开成下降幂以后，$f(x)$ 可以写成 $\prod_i (x-i)^{c_i}$ 的形式，我们找到 $P$ 的一个原根 $g$，令 $\log_g(x)$ 为 $x$ 的离散对数，则只需要计算 $\log_g f(x)=\sum_{i}c_i \log_g(x-i)$，这显然是一个卷积，可以在 $O(P\log P)$ 时间内解决。

K. Talk Event

先排除掉总票数不超过 $X$ 的情况。如果总票数超过 $X$，那么选择的中奖者的总票数只可能是 $X$ 到 $X-3$。我们枚举选出的总票数是 $X-i$，那么购买票数不超过 $i$ 的人必须被选。现在问题归约到了求选出 $K$ 个人，使得他们的总票数恰好是 $X$ 的方案数。这等于 $$ [x^Xy^K]\frac{(1-(xy)^{T_1+1})(1-(x^2y)^{T_2+1})(1-(x^3y)^{T_3+1})(1-(x^4y)^{T_4+1})}{(1-xy)(1-x^2y)(1-x^3y)(1-x^4y)} $$ 枚举分子的项，问题转化为分子为 $1$ 的情况。令 $Q(x,y)=(1-xy)(1-x^2y)(1-x^3y)(1-x^4y)$，则 $$ \frac{P(x,y)}{Q(x,y)}=\frac{P(x,y)Q(x,-y)}{Q(x,y)Q(x,-y)}=\frac{P(x,y)Q(x,-y)}{Q(x^2,y^2)} $$ 分子上必须取 $x,y$ 次数奇偶性分别等于 $X,K$ 的项，然后就会递归到 $N,K$ 都减半的子问题，且 $P(x,y)$ 因为每次先乘上 $Q(x,-y)$ 再次数减半，因此其次数永远不会超过 $Q$ 的次数。递归到 $N=K=0$ 时答案即为 $P(x,y)$ 的常数项。这个过程也可以用数位 DP 来理解，也就是考虑把每一种人选的数量二进制分解，然后状态记录总和和人数的进位。时间复杂度 $O(\log X)$。

L. Unique Sheet

注意到只出现一次的数的行列不能被删除，而这样的数的数量至少是 $2(N-K)^2-N^2=(N-2K)^2-2K^2$，因此当 $N$ 较大时剩下的行列数量总和不超过 $4K$。这时可以直接枚举选择的行列集合然后判断。当 $N$ 较小时剩的数量可能较多（例如 $N=16,K=5$ 可以做到每个数都出现两次），可以先枚举行之后再进行一次这样的剪枝，然后再枚举列。

但是注意枚举选择的行列之后还是需要 $O(NK)$ 的时间进行判断，可以用异或哈希将这个判断优化到 $O(K)$。

M. Up-Down Sequence

设 $f(P)$ 为排列 $P$ 的长度为 $3$ 的上升子序列数量，则要构造满足 $f(P)=f(P^R)$ 的排列，其中 $P^R$ 是 $P$ 的翻转。因为 $f(P)=f(P^{-1})$，只要 $P^{-1}=P^R$ 就一定满足，这也就等价于 $P(P(i))=N+1-i$。这样就容易构造 $N\bmod 4=0,1$ 的情况。

对于 $N\bmod 4=2,3$ 的情况，我们可以令 $P_1=1,P_N=2$，然后对于中间的 $N-2$ 个位置用上述构造。因为涉及到 $P_1$ 和 $P_N$ 的贡献只取决于中间的长度为 $2$ 的上升和下降子序列数量，而在上述构造上它们也是相等的。