D. Ears

题目大意：给定数轴上的区间 \([0, L]\)，将数轴分成了 \(L\) 段，每段有一个数字 \(a_i\)。你可以画一条折线（从某个整数开始，在某个整数结束），设每段被覆盖的次数是 \(b_i\)。最小化 \(\sum |a_i-b_i|\)。

题解：假设我们知道了起点和终点，那么数轴被分成了三段，第一段的 \(b_i\) 是偶数，第二段是奇数，第三段是偶数。

注意第一段非零的 \(b_i\) 是连续的一段，并且紧接在第二段之前；同理，第三段中非零的也是连续的一段，紧接在第二段之后。于是我们可以把区间分成五段，直接 dp 即可。注意处理 \(a_i=0\) 位置的时候，贡献与通常的偶数 \(a_i\) 不同。

E. Odd Subrectangles

题目大意：给定一个 \(n\times m\) 的 0/1 矩阵，有多少种选择行指标 \(A\)，列指标 \(B\) 的方案数，使得这 \(|A|\times |B|\) 个元素的和是奇数。

题解：假设我们选定了行指标 \(A\)，合法的列指标有多少种方案呢。如果这些行向量相加（以下均为模 \(2\) 意义下）为 \(0\) 向量，那么方案数为 \(0\)。否则，假设有 \(x\) 个 \(1\)，那么方案数为 \(2^{m-x}\times \left({x\choose 1}+{x\choose 3}+{x\choose 5}+\cdots \right)=2^{m-1}\)。

接下来的问题便是有多少个相加不为 \(0\) 的行指标 \(A\)。考虑反面，显然有 \(2^{n-\text{rank}}\) 个相加为 \(0\) 的行指标 \(A\)（对于非基行指标相加的非 \(0\) 向量，可以将其对应表示的基向量加入指标集）。

所以答案为 \((2^n-2^{n-\text{rank}})\cdot 2^{m-1}\)。

F. Pass

题目大意：\(n(n\leq 3000)\) 个人排成一行，第 \(i\) 个人有一个属性 \(a_i\in \{0, 1, 2\}\)，分别表示他有两个红球/一个红球一个蓝球/两个蓝球。进行 \(2n\) 次操作，每次操作的时候，每个手上有球的人，选择一个球给第 \(i-1\) 个人。第 \(1\) 个人的球放在一个序列后端。问有多少种本质不同的序列。

题解：构造一种计数，使得本质不同序列和构造一一对应，本题中我们只需要假设同色球的相对顺序不变（初始同一个人手上的同色球假设有序）。同时注意到第 \(i\) 个人手中的红球可以放在序列的任意不小于 \(i\) 的下标处；对蓝球同理。

设 \(\text{dp}[i][j]\) 表示现在序列中一共有 \(i\) 个球，其中有 \(j\) 个是红球。假设从 \(\text{dp}[i-1][j]\) 转移，枚举第 \(i\) 个球的颜色，如果是红色，需要满足第 \(j+1\) 个红球所属的人编号不超过 \(i\)，转移到 \(\text{dp}[i][j+1]\)；如果是蓝色，需要满足第 \(i-j\) 个蓝球所属的人编号不超过 \(i\)，转移到 \(\text{dp}[i][j]\)。