性质的必然存在性.jpg
注意到题目给出了十分特殊的性质 \(\boldsymbol{k\le n}\)，因此考虑从这个地方入手。
注意到当 \(k<n\) 时，根据抽屉原理可知必然存在一个全 \(0\) 行，因此考虑枚举该行，然后对于该行内每个 \(1\)，翻转该位置对应的列。此时剩下的行要么翻转要么不翻转，且这些行均独立。因此设此时第 \(i\) 行有 \(d_i\) 个 \(1\)，那么最少需要执行 \(\sum\limits_{j\neq i}\min(d_j,n-d_j)\)（\(i\) 表示枚举的是第 \(i\) 行全 \(0\)），容易发现这个东西可以用 bitset 优化到 \(O(\frac {n^3}{\omega})\)。列的情况同理。
而 \(k=n\) 时唯一的特殊情况是每一行每一列都有恰好一个 \(1\)。此时考虑枚举第一行 \(1\) 的位置，然后可以确定剩余位置全部为 \(0\)，转化为第一种情况，同样可以用 bitset 优化到 \(O(\frac{n^3}{\omega})\)。因此本题得解，总时间复杂度为 \(O(\frac{n^3}{\omega})\) 可以通过。
代码十分好写。
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ld = long double;
const int N = 1010;
int f[N];
char s[N][N];
bitset<N> bit[N];
signed main()
{cin.tie(0)->sync_with_stdio(false);cout << fixed << setprecision(15);int n, k;cin >> n >> k;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)cin >> s[i][j], bit[i - 1].set(j - 1, s[i][j] == 'o');if (n == k){for (int i = 1; i <= n; ++i){// s[1][i] = 1// s[1][j] = 0 (i != j)bit[0].flip(i - 1);int sum = 1;for (int j = 2; j <= n; ++j){int cnt = bitset(bit[0] ^ bit[j - 1]).count();sum += min(cnt, n - cnt);}if (sum <= k){cout << "DA\n";return 0;}bit[0].flip(i - 1);}for (int i = 1; i <= n; ++i){int sum = 0;for (int j = 1; j <= n; ++j)if (i != j){int cnt = bitset(bit[i - 1] ^ bit[j - 1]).count();sum += min(cnt, n - cnt);}if (sum <= k){cout << "DA\n";return 0;}}cout << "NE\n";}else{for (int i = 1; i <= n; ++i){int sum = 0;for (int j = 1; j <= n; ++j)if (i != j){int cnt = bitset(bit[i - 1] ^ bit[j - 1]).count();sum += min(cnt, n - cnt);}if (sum <= k){cout << "DA\n";return 0;}}cout << "NE\n";}return 0;
}