Discussion #1494 - Problem #17430

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

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

Comments