AT_yahoo_procon2019_qual_e Odd Subrectangles 题解

· · 题解

首先，我们称一个合法的行的选取方案当且仅当我们能选出一列，使这一列上的与行的交点的值异或起来是 1。这样其他列就可以任意选了。若选完异或和为 0，异或上这一列，否则不异或。在排除一列后，这个选法的贡献是 2^{m-1} 的。

现在考虑怎样算出合法的行选取方案的个数。一个选法不合法当且仅当不存在有一列异或和为 1 的列。我们将一行视作一个二进制数，这样问题就变为了选取一些数，使异或和为 0。这就可以用线性基来做。设 x 为不在线性基内的数的个数，则答案为 2^x。因为每一个不在线性基内的数都可以用线性基内的数表示出来，我选这个数后将线性基中对应的子集拿出来异或在一起，异或和一定为 0。

所以最终答案就是 (2^n-2^x)\times2^{m-1}

代码：

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=300+10,mod=998244353;
int n,m;
bool a[N][N];
bitset<N> d[N],num;
int siz;
void insert(int id)
{
    for(int i=1;i<=m;i++)
        num[i]=a[id][i];
    for(int i=m;i>=1;i--)
    {
        if(num[i]==0)
            continue;
        if(d[i]==0)
        {
            d[i]=num;
            siz++;
            break;
        }
        num^=d[i];
    }
}
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        insert(i);
    cout<<((qpow(2,n)-qpow(2,n-siz))%mod+mod)%mod*qpow(2,m-1)%mod<<endl;
    return 0;
}