NFLSPC #8 题解

考虑一维情况如何解决。可以排序后选择前 $n + 1$ 个点，找出其中颜色相同的一对，连接这对点并把前面不同颜色的删除，这样对于剩下 $n - 1$ 种颜色，至少有 $n$ 个点，转化为等价子问题。 对于二维的情况，观察到限制实际上被放松了，因此按照 $x$ 轴排序后做一维的情况，容易验证不会相交。时间复杂度 $\mathcal O(n ^ 2 \log n)$。

首先，需要发现，在题目条件的限制下，有唯二解的题面，唯二解差异涉及的地方，一定只涉及恰好某两个数字。

下面考虑构造。不难发现，一共只有两个数字的情况，差异只可能是偶数，涉及恰好 $x$ 个宫，$x$ 个行，$x$ 个列，满足每行、每列、每宫都恰好含有涉及的两个数字各一个，而且不能由多个独立结构组成，否则解的数量不是 $2$ ，容易变为 $2^y$ 其中 $y$ 为相互独立的该种结构数量。自然发现，该种结构是类似于哈密尔顿回路的。因此，直接枚举所有2个数字的组合，然后排除掉已经有这两个数字的行、列、宫。剩下的里面，可用的行、列、宫的最小值即为这两个数可能达到的最大差异值的一半，注意排除不可用的宫，如果一个宫只剩少于2个空格，这个宫也是不可用的。

找到全局可能达到的差异值最大的那组数，然后，在此基础上，搜索出一组满足条件的填法两个数字填法。这时，我们有很大概率有至少一组合法的数独解，然后再搜出任意一组整个数独的解，然后把输入的数和这个两个数字差异部分全部去掉，这样组合的补法就有唯二解了。

不会

容易把每个位置贡献拆开来，根据对称性发现每个位置对自己和对别人的贡献分别相同，并且都形如当前值乘以某个系数。容易发现每轮这两个系数分别是 $x\leftarrow kx+b$ 的形式，做 $k$ 次一次函数复合即可，这里类似快速幂。复杂度 $O(n+\log k)$。

考虑 $n\leq19$。此时利用 product trick 将所求化为每个点选一条与其相连的边或不选（不选的贡献是 $t$）。此时状压每个点选没选，然后依次加入每条边更新 dp 数组，复杂度 $O(m2^n)$。

对于 $n$ 大的情况，按除以 $k$ 的商分层，依次考虑每一层，同样加边并维护当前层和下一层的状态即可 $O(m2^{2k})$。

此时我们发现可以删掉已经处理完与其相连的所有边的点，那么现在按连接的点的顺序加入边可以做到 $O(m2^{1.5k})$。

我们先处理完连接一个和零个下一层点的当前层的点。对于剩下的点，我们在其连接的两个点之间建立虚边，形成了很多连通块，我们按非树边数量从大到小遍历每个连通块，访问一条边就处理其代表的上一层的点即可。可以证明此时复杂度 $O(m2^k)$，可以通过。

一次操作相当于选出一些下标，相邻的选出的下标奇偶性不同，然后全部 $-1$，不能选 $0$。

我们先考虑没有 $0$ 的时候，答案一定是所有数的 $\max$。

那么考虑把有 $0$ 的情况转化成没有 $0$ 的情况，我们观察到 $x00\dots 00y$ 可以做一个缩的操作。

如果有奇数个 $0$，缩成 $x, y$，否则缩成 $x+y$，正确性不难证明。

这样我们维护这个东西扫描的过程，类似一个栈，用线段树二分维护就行了，复杂度 $\mathcal O(n\log n)$。

$f_i$ 表示第 $i$ 行作为 $n,m$，以 $i$ 行为开始的后缀的方案数，每行的转移点是一个固定位置，只需要判一下区间最大值是否不超过 $m$。最后枚举第二行的 $n$ 即可。复杂度 $O(n\log n)$。

不会

不会