可是我的自卑胜过了一切爱我的

· · 题解

首先题意可以转化为用若干次 1, 2 操作使得矩阵中至多 k 个 1, 并且操作顺序是无所谓的。

乍一看不可做，观察一下有什么性质？k \le n 非常重要。

先考虑 k < n, 因为此时根据抽屉原理，肯定有一行会在 1, 2 操作完后全部变成 0, 考虑枚举这一行，就可以得出每一列是否操作，列操作序列就等于这一行的序列（不用考虑这一行是否操作，因为这一行翻转了相当于别的所有行都翻转），将别的行用列操作翻转后，不进行操作就需要 1 的个数次操作 3, 否则需要 0 的个数次操作 3, 取 \mathrm{min} 后判断总操作次数是否 \le k 即可。

然后考虑 k = n, 此时上面的策略也是成立的，但是多了一种情况：操作 1, 2 完成后，每行恰好有一个 1, 这样正好是 n 次操作 3, 考虑枚举第一行 1 的位置，然后同上得出列的操作序列，再判断其余每行操作/不操作后是否只有一个 1 即可。

上述操作都可以用 bitset 维护。

时间复杂度 \mathcal{O}(\dfrac{n^3}{\omega})

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e3 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {
    cout << arg << ' ';
    dbg(args...);
}
int n, k;
char s[N][N];
bitset<N>f[N];
int main() {
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> (s[i] + 1);
        for (int j = 1; j <= n; j++) f[i][j] = (s[i][j] == 'o');
    }
    if (k == n) { // 可能有操作 3 前每行恰好一个 1 的情况
        for (int i = 1; i <= n; i++) {
            f[1].flip(i);
            bool ok = 1;
            for (int j = 2; j <= n && ok; j++) {
                f[j] ^= f[1];
                if (min(f[j].count(), n - f[j].count()) > 1) ok = 0;
                f[j] ^= f[1];
            }
            if (ok) { cout << "DA\n"; return 0; }
            f[1].flip(i);
        }
    }
    for (int i = 1; i <= n; i++) { // 这一行不需要提前翻转，因为这一行的翻转相当于除了它的每一行都翻转
        int sum = 0;
        for (int j = 1; j <= n; j++) if (i != j) {
            f[j] ^= f[i];
            sum += min(f[j].count(), n - f[j].count());
            f[j] ^= f[i];
        }
        if (sum <= k) { cout << "DA\n"; return 0; }
    }
    cout << "NE\n";
    return 0;
}