[Atcoder Yahoo Contest 2019]E.Odd Subrectangles(思维+线性基)

Score : $800$ points

题面

传送门
翻译有时间再补…

题解

很巧妙的一道题。
在此特别感谢一下SovietPower的博客文章。

首先这是一个01矩阵，因此可以将和的奇偶性看成是异或和是否为1。
按照题解的套路，假如我们已经选好了一些列。
这样的话我们可以确定每行的异或和是$0$还是$1$。
设有$a$行异或和为$1$，$b$行异或和为$0$，显然有$a+b=m$。
题目要求总异或和为$1$，可以在$a$行中选奇数行，$b$列中随便选。
$a$行中选奇数行的方案数是:$C_a^1+C_a^3+...=2^{a?1}$(可以查一下杨辉三角的性质)
因此确定一些列的方案数是$2^{a?1}?2^b=2^{m?1}$.
但是如果$a=0$时，是不满足条件的。
考虑统计这些不合法的情况。
可以转换为将每一行都看成一个二进制数列，统计一下其中子集异或和为0的个数。
这是可以用线性基解决的经典问题。
根据线性基的结论，在线性基里选取任意子集的异或和都不为0。
设线性基的大小为$r$，那么异或等于零的个数就是$2^{n?r}$
那么总答案就是$(2^n?2^{n?r})?2^{m?1}$。
二进制数列可以用bitset优化一下。
因此时间复杂度为$O(\frac{n^3}{w})$。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
using namespace std;
#define MAXN 300
#define MOD 998244353
int n,m;
bitset<MAXN+5> A[MAXN+5],B[MAXN+5];
int read()
{
    int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*f; 
}
int fst_pow(int a,int b)
{
    int res=1;while(b){
    if(b&1)res=(1LL*res*a)%MOD;a=(1LL*a*a)%MOD;b>>=1;}return res;
}
int main()
{
    scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)A[i][j]=(read()==1);int r=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(A[i][j]){
    if(B[j][j])A[i]^=B[j];else{
    B[j]=A[i];r++;break;}}printf("%d",(fst_pow(2,n+m-1)-fst_pow(2,n-r+m-1)+MOD)%MOD);
}