题解：CF1605F PalindORme

· · 题解

duel 随到了这题，耗时 4h 切掉。

套路的，考虑对这个东西进行刻画。

考虑到如果存在 a_i=a_j(i\neq j)，那么可以直接将 a_i,a_j 放到序列两端一定不劣。那么 a_i 二进制下为 1 的位就不会有任何限制了，可以把所有数的这些位去掉，这样就成了一个子问题。

那么递归何时终止呢？首先观察发现 0 并不会对结果造成影响，不妨去掉（但是奇偶性仍然不变）。那么如果所有数都被清空了，一定可以。按照递归过程构造就是一组答案。如果只剩 1 个数并且一开始序列长为奇数，那么显然也是可以的。

那么何时无解？在不满足有解的判定下如果不存在 a_i=a_j(i\neq j)，则无解。此时显然无法继续构造，而之前的构造是最优的。

为了避免 0 的 corner case，不妨假设我们所求的 \{a\} 均为正整数。

考虑 dp。直接设 dp_{i,j} 为 n=i,k=j 时的答案，考虑转移。上述分析对无解情况的刻画比较明确，不妨正难则反，计算不合法的 \{a\} 的数量，然后单步容斥。

考虑每个问题只与长度和值域有关，不妨枚举无解的子问题。

设 n=i,k=j 的子问题为 n=x,k=y，那么发现不是子问题的这 i-x 个数单独拎出来是合法的。于是这一部分的答案就是 dp_{i-x,j-y}。考虑剩余的 x 个数。它们只取 y 位的部分是不能相同的，并且是不能取 0 的（不然就可以归到前 i-x 个数中）。那么它们的取法有 \frac{(2^y-1)!}{(2^y-1-x)!} 种。考虑它们的 j-y 位怎么取。这没有任何限制，也就是 2^{x(j-y)} 种取法。最后再乘上 x 个数、y 个位的位置的情况。也就是 C_i^x\times C_j^y。

同时，如果 x=0，那么这种情况显然不能被减去；如果 i 为奇数且 x=1，那么这种情况也不能被减去。

但是这样会有两个问题：

先考虑第一个问题。分析后会发现这个问题产生的原因是有空白位（该位上所有数都是 1）导致这一位的归属（即在 y 还是在 j-y 里记）存在多种情况导致算重。那么解决办法很简单：钦定 dp_{i,j} 中的 j 个位必须都不为空。那么如何计算？之前转移显然是不变的，但是最终算出来的答案显然不满足条件。考虑继续容斥：若某情况不满足条件，那么其去掉空白位后一定和某个 dp_{i,k}(k<j) 中的情况一致。于是容斥。发现 dp_{i,k} 的每个情况恰好会排除 C_j^k 种 dp_{i,j} 的情况，那么 dp_{i,j} 需要减去 C_j^k 倍的 dp_{i,k}。

对于第二个问题，方法很简单：再定义一个 f_{i,j} 表示 n=i,k=j 并且必须消完的合法数量，则 dp 转移时的所有 dp 转为 f 即可。f 与 dp 的差别即为当 i 为奇数且 x=1 时，这种情况也需要被减去。

那么就做完了。时间复杂度 O(n^2k^2)，题面中 n,k\le 80 具有一定误导性，我一开始以为是五次方做法。