题解：AT_yahoo_procon2019_qual_e Odd Subrectangles

· · 题解

题意

给定一个 n\times m 的 \texttt{01} 矩阵 A，现在你要选出若干行与若干列，这些行与列会产生若干个交点，设这些交点的集合为 S=\{(x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)\}，求有多少种选法使得 \sum_{i=1}^k A_{x_iy_i}\bmod2=1 即交点权值和为奇数，答案对 998244353 取模。

题解

首先，权值和为奇数相当于权值异或和为 1。考虑这样一件事情：我们钦定了若干行 l_1,l_2,\cdots,l_p，如果存在一个 q，满足第 q 列上第 l_1,l_2,\cdots,l_p 行的权值异或和为 1，那么有一种选择的方案是：先不选第 q 列，其他列随便选，若选完后发现交点异或和是 0，则选第 q 列使异或和变为 1，否则不选。显然这个选择方案囊括所有合法情况，此时对答案的贡献为 2^{m-1}。

若找不到这样一个 q 呢？显然此时对答案无贡献。不妨考虑把每一行从左到右看成一个二进制数，那么不存在这个 q，当且仅当所有选中的行对应的二进制数的异或和为 0。

这个问题等价于，给你 n 个数，要你求所有异或和为 0 的子集的数量。考虑线性基，先把所有数插进去，设此时线性基大小为 k，那么答案就是 2^{n-k}。原理和上面选列的方案差不多，考虑线性基外元素任选，得到一个异或和，再把这个异或和拿到线性基里选数异或成 0，由线性基定义可知一定选的出来。

综上，答案为 (2^n-2^{n-k})\times 2^{m-1}。我们需要一个可以处理 2000 位二进制数的线性基，大力 bitset 即可通过，时间复杂度 O\left(\cfrac{nm^2}w\right)。

代码

#include <bits/stdc++.h>
bool MemoryST; using namespace std;
#define ll long long
#define mk make_pair
#define open(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define abs(x) (((x) > (0)) ? (x) : (-(x)))
#define lowbit(x) ((x) & (-(x)))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define BCNT __builtin_popcount
#define cost_time (1e3 * clock() / CLOCKS_PER_SEC) << "ms"
#define cost_space (abs(&MemoryST - &MemoryED) / 1024.0 / 1024.0) << "MB"
const int inf = 0x3f3f3f3f; 
const ll linf = 1e18; 
mt19937 rnd(random_device{}());
template<typename T> void chkmax(T& x, T y) { x = max(x, y); }
template<typename T> void chkmin(T& x, T y) { x = min(x, y); }
const int maxn = 2005, P = 998244353;
namespace ModOptions_normal {
    int add(int x, int y) { return (x + y) % P; } void addto(int &x, int y) { (x += y) %= P; }
    int mul(int x, int y) { return 1ll * x * y % P; } void multo(int &x, int y) { x = mul(x, y); }
    int qp(int x, int y) {
        int res = 1; for (; y; y >>= 1, multo(x, x))
            if (y & 1) multo(res, x);
        return res;
    } int divv(int x, int y) { return 1ll * x * qp(y, P - 2) % P; } void divto(int &x, int y) { x = divv(x, y); } 
    int sub(int x, int y) { return (x + P - y) % P; } void subto(int &x, int y) { x = sub(x, y); }
} using namespace ModOptions_normal;
int n, m, a[maxn][maxn];
namespace LinearBasis {
    bitset<maxn> b[maxn], cur;
    int siz = 0;
    void insert(int p) {
        for (int i = 1; i <= m; i ++)
            cur[i] = a[p][i];
        for (int i = 1; i <= m; i ++) if (cur[i]) {
            if (!b[i][i]) return siz ++, b[i] = cur, void(0);
            cur ^= b[i];
        }
    }
} using namespace LinearBasis;
bool MemoryED; int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);
        insert(i);
    } printf("%d\n", mul(sub(qp(2, n), qp(2, n - siz)), qp(2, m - 1)));
    return 0;
}