8.3 CSP 模拟 13

\(\text{zero4338 round}\)

T1 y

显然 \(\text{xt}\) 会选择四个角，对每个格子求出到四个角的曼哈顿距离最大值，操作一定会优先选择最大值较小的，所以把距离数组排个序就行了。

T2 s

经典套路是设答案是 \(a\)，把小于 \(a\) 的位置设成 \(0\)，大于等于设成 \(1\)，这样按照操作序列进行一次操作之后结果为 \(0\) 则答案加 \(1\)，容易发现如果原排列结果是 \(a\)，那么在 \(1\sim a\) 都有一次贡献，等价于加 \(a\)。

考虑 DP，设 \(f_{i,j,0/1}\) 前 \(i\) 个操作，排列上有 \(j\) 个 \(1\)，当前结果是 \(0/1\) 的方案数。转移平凡，复杂度 \(O(n^2)\)。

答案还要乘上 01 序列对应排列的个数 \(j!\times (n-j)!\)。

如果每个连续段看作整体 DP 也可以。也有看作多项式平移再矩阵加速的做法，目测常数较大。

T3 p

去年不会，今年还不会。

两个区间并的直径端点一定在两个区间直径端点中。线段树维护。

T4 m

容易想到二项式反演。

钦定 \(i\) 个不合法，枚举有 \(j\) 个只包含 \(1\) 次，再枚举有 \(k\) 个集合中包含钦定的这些元素，那么这些集合的其余 \(n-i\) 的元素暴力选，而另外的集合选择方案数理应是 \(\sum_{l=0}^{2^n-k}\dbinom{2^{n-i}}{l}\)，而由于 \(k\le i\)，\(2^n-k\ge 2^{n-i}\)，所以就是 \(2^{2^{n-i}}\)。

\[f(i)=\dbinom{n}{i}\sum_{j=0}^i\dbinom{i}{j}\sum_{k=0}^j\begin{Bmatrix}j\\k\end{Bmatrix} (2^{n-i})^k2^{2^{n-i}} \]

套上二项式反演再整理一下就是：

\[g(0)=\sum_{i=0}^n (-1)^i2^{2^{n-i}}\dbinom{n}{i}\sum_{k=0}^i (2^{n-i})^{k}\sum_{j=k}^i \dbinom{i}{j}\begin{Bmatrix}j\\k\end{Bmatrix} \]

后面这个式子考虑组合意义，从 \(i\) 个元素中选取若干加入到 \(k\) 个集合，要求集合非空，可以递推，大致是 \(F_{i,k}=(k+1)F_{i-1,k}+F_{i-1,k-1}\)，也就是每个元素可以选择放或不放、加入或新建一个集合。

这样就 \(O(n^2)\) 解决了。