Problem:


Score : 800 points

Problem Statement

There is a square grid with N rows and M columns.
Each square contains an integer: 0 or 1. The square at the i-th row from the top and the j-th column from the left contains a_{ij}.

Among the 2^{N+M} possible pairs of a subset A of the rows and a subset B of the columns, find the number of the pairs that satisfy the following condition, modulo 998244353:

The sum of the |A||B| numbers contained in the intersection of the rows belonging to A and the columns belonging to B, is odd.

Constraints

1 \leq N,M \leq 300

0 \leq a_{i,j} \leq 1(1\leq i\leq N,1\leq j\leq M)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_{11} ... a_{1M}
:
a_{N1} ... a_{NM}

Output

Print the number of the pairs of a subset of the rows and a subset of the columns that satisfy the condition, modulo 998244353.

Sample Input 1

2 2
0 1
1 0

Sample Output 1

6

For example, if A consists of the first row and B consists of both columns, the sum of the numbers contained in the intersection is 0+1=1.

Sample Input 2

2 3
0 0 0
0 1 0

Sample Output 2

8



Sample input:
2 2
0 1
1 0


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
class GE():
    def __init__(self, A, mod):
        self.N = len(A)
        self.M = len(A[0])
        self.A = A[:]
        self.mod = mod
        self.uptri = None
        self.pivot = []
        self.R = None
        
    def ut(self):
        if self.uptri is not None:
            return self.uptri
        self.uptri = self.A[:]
        
        c = 0
        for i in range(self.N):
            if i + c >= self.M:
                break
            while self.uptri[i][i+c] == 0:
                for j in range(i+1, self.N):
                    if self.uptri[j][i+c]:
                        self.uptri[i], self.uptri[j] = self.uptri[j], self.uptri[i]
                        break
                else:
                    c += 1
                    if i + c == self.M:
                        return self.uptri
            self.pivot.append((i, i+c))
            t = pow(self.uptri[i][i+c], self.mod - 2, self.mod)
            for j in range(i+1, self.N):
                tj = t * self.uptri[j][i+c]
                self.uptri[j][i+c:] = [(aj - tj*ai) % self.mod for ai, aj in zip(self.uptri[i][i+c:], self.uptri[j][i+c:])]
            for pi, pj in self.pivot[::-1]:
                t = pow(self.uptri[pi][pj], self.mod-2, self.mod)
                self.uptri[pi][pj:] = [(ai * t) % self.mod for ai in self.uptri[pi][pj:]]
                for i in range(pi-1, -1, -1):
                    ti = self.uptri[i][pj]
                    self.uptri[i][pj:] = [(ai - api*ti) % self.mod for ai, api in zip(self.uptri[i][pj:], self.uptri[pi][pj:])]
        
        return self.uptri
    def rank(self):
        if self.R is not None:
            return self.R
        self.ut()
        self.R = len(self.pivot)
        return self.R

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
mod = 998244353
T = GE(A, 2)
print((pow(2, N+M-1, mod) - pow(2, N+M-T.rank()-1, mod)) % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import random

mod=998244353


n,m=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]

#n,m=10,10
#A=[[int(random.randint(0,1)) for j in range(m)] for i in range(n)]


#A=np.array(A)

#print(A)
i=0
j=0
while i<n and j<m :
    #for ii in range(len(A)):
        #print(A[ii])
    #print("\n")
    t=0
    #print(A[i][j])
    if A[i][j]==0 :
        #print("B")
        k=i
        while k<n and A[k][j]==0 :
            k+=1
        #print(str(i)+" "+str(k))
        if k<n :
            #print(A)
            #B=[A[i][0],A[i][1]]
            #A[i]=[A[k][0],A[k][1]]
            #A[k]=[B[0],B[1]]
            for u in range(m):
                A[i][u],A[k][u]=A[k][u],A[i][u]

            #print(A)
        else :
            t=1
            j+=1
    #print(t)
    if t==0 :
        #print("A")
        #print(i)
        for p in range(i+1,n):
            #print("AA")
            if A[p][j]>0 :
                #print(p)
                for kk in range(m):
                    A[p][kk]=(A[p][kk]-A[i][kk])%2
        i+=1
        j+=1


#for i in range(len(A)):
#    print(A[i])

r=0
j=0
for i in range(m):
    if j<n :
        if A[j][i]!=0 :
            r+=1
            j+=1

for i in range(n):
    for j in range(m):
        A[i][j]=int(A[i][j])
#print(A)
#print(r) #rank

a=1
b=1

for i in range(n+m-1):
    a=(a*2)%mod
for i in range(n+m-1-r):
    b=(b*2)%mod

print((a-b)%mod)

Submission status: Time Limit Exceeded

Solution code:
# from : https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4212377
H,W = map(int, input().split())
A = [ [int(j) for j in input().split()] for _ in range(H)]
MOD = 998244353

piv = 0

# Gaussian Elimination to calculate rank of the matrix A
for w in range(W): # fix column, 
    r = -1
    for h in range(piv, H):
        if A[h][w] == 1:
            r = h
            break
    if r == -1: # there is no odd cell for all the rows inside intersections.
        continue 

    # You want to set ODD ROW ( A[h][w] == 1 ) into pivot row.
    if r != piv: # already, skip.
        for j in range(W): # swap rows
            A[r][j], A[piv][j] = A[piv][j], A[r][j]

    for h in range(H):
        if h != piv and A[h][w] == 1: # really needed?
            for j in range(W):
                A[h][j] ^= A[piv][j] # for other rows, erase ...
                # Hakidashi method: http://senkei.nomaki.jp/gaussian_elimination.html
                # https://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E3%81%AE%E6%B6%88%E5%8E%BB%E6%B3%95 : Gaussian Elimination
    piv += 1


# print("----output matrix ----")
# for h in range(H):
#     print(A[h])
# exit(0)


# from pprint import pprint; pprint(A)

ret = 1
ret = pow(2, H, MOD)
# for h in range(H):
#     ret = ret * 2 % MOD

sub = 1
# for i in range(H-piv):
#     sub = sub * 2 % MOD
sub = pow(2, H-piv, MOD)


ret += MOD - sub          # ret = 2^N - 2^(N-r)
ret %= MOD

for i in range(W-1):      # ret *= 2^(M-1)
    ret = ret * 2 % MOD

# from editorial  : https://img.atcoder.jp/yahoo-procon2019-qual/editorial.pdf
# rank : r 
# 2^(N+M-1) - 2^(N+M-r-1)

print(ret % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
aij = np.zeros((N,M),dtype=int)
for i in range(N):
  lst = list(map(int, input().split()))
  for j, aj in enumerate(lst):
    aij[i,j] = aj

total = 0
for i in range(N):
  for j in range(N+1):
    for k in range(M):
      for l in range(M+1):
        part = aij[i:j, k:l]
        if np.sum(part) % 2 != 0:
          total += np.sum(part)
print(total)

Submission status: Accepted

Solution code:
N,M=map(int,input().split());B=[]
for i in[0]*N:
    s=int(input().replace(" ",""),2)
    for b in B:s=min(s,s^b)
    B+=[s]*(s!=0)
N+=M-1;print((2**N-2**(N-len(B)))%998244353)

Submission status: Accepted

Solution code:
I=input;N,M=map(int,I().split());B=[]
for i in range(N):
    s=int(I().replace(" ",""),2)
    for b in B:s=min(s,s^b)
    if s!=0:B.append(s)
N+=M-1;print((2**N-2**(N-len(B)))%998244353)

Submission status: Accepted

Solution code:
N,M=map(int,input().split());mod=998244353;B=[]
for i in range(N):
    s=int(input().replace(" ",""),2)
    for b in B:s=min(s,s^b)
    if s!=0:B.append(s)
print((pow(2,N+M-1,mod)*(1-pow(2,mod-1-len(B),mod)))%mod)

Submission status: Accepted

Solution code:
N,M=map(int,input().split());mod=998244353;base=[]
for i in range(N):
    A=input().split();s=sum(int(A[j])*2**j for j in range(M))
    for b in base:s=min(s,s^b)
    if s!=0:base.append(s)
res=N-len(base);print((pow(2,N+M-1,mod)-pow(2,M-1+res,mod))%mod)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(N):
    a.append(list(map(int,input().split())))
mod=998244353

B=[]
for i in range(M):
    b=0
    for j in range(N):
        b+=a[j][i]*2**j
    B.append(b)

base=[]
for i in range(M):
    t=B[i]
    for b in base:
        t=min(t,t^b)
    if t!=0:
        base.append(t)

res=M-len(base)
ans=pow(2,N-1,mod)*(pow(2,M,mod)-pow(2,res,mod))
print(ans%mod)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(N):
    a.append(list(map(int,input().split())))
mod=998244353

B=[]
for i in range(M):
    b=0
    for j in range(N):
        b+=a[j][i]*2**j
    B.append(b)

base=[]
for i in range(M):
    t=B[i]
    for b in base:
        t=min(t,t^b)
    if t!=0:
        base.append(t)

res=M-len(base)
ans=pow(2,N-1,mod)*(pow(2,M,mod)-pow(2,res,mod))
print(ans%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[int(input().replace(" ",""),2) for i in range(n)]
o=998244353
c=0
for j in range(m)[::-1]:
 for i in range(c,n):
  if a[i]&1<<j:
   for k in range(n):
    if i!=k and a[k]&1<<j:a[k]^=a[i]
   a[i],a[c]=a[c],a[i];c+=1
p=lambda x:pow(2,x,o)
print(p(n+m-c-1)*(p(c)-1)%o)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[int(input().replace(" ",""),2) for i in range(n)]
o=998244353
c=0
for j in range(m)[::-1]:
 for i in range(c,n):
  if a[i]&1<<j:
   for k in range(n):
    if i!=k and a[k]&1<<j:
     a[k]^=a[i]
   a[i],a[c]=a[c],a[i]
   c+=1
p=lambda x:pow(2,x,o)
print(p(n+m-c-1)*(p(c)-1)%o)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [int(input().replace(" ",""),2) for i in range(n)]
mod = 998244353
cnt = 0
for j in range(m)[::-1]:
  for i in range(cnt,n):
    if a[i] & 1<<j:
      for k in range(n):
        if (i != k) and (a[k] & 1<<j):
          a[k] ^= a[i]
      a[i],a[cnt] = a[cnt],a[i]
      cnt += 1
if cnt == 0:
  print(0)
else:
  ans = pow(2,n+m-2*cnt,mod)*pow(2,cnt-1,mod)*(pow(2,cnt,mod)-1)%mod
  print(ans)

Submission status: Accepted

Solution code:
import sys

# この２行は
#   a   1 0 1 0
#   b   1 1 0 0
# こうしても、作れる集合の内訳が変わらない
#   a   1 0 1 0
#   b^a 0 1 1 0
# {両方未選択, 上だけ選択, 下だけ選択, 両方選択}: {φ, a, b, a^b} == {φ, a, b^a, b}
# これは列方向に対しても同じことなので、掃き出し法チックなことをして
#   1 0 ... 0 0 0
#   0 1 ... 0 0 0
#   : :     : : :
#   0 0 ... 1 0 0
#   0 0 ... 0 0 0
# こんな形にできる
# ここで、行の選び方で'1'のある行を1つでも含むような選び方は、
# その'1'の場所の列(どれでもいいので1つ)を選択するかしないかで、
# 全体の和が偶数, 奇数となるパターンがちょうど半分ずつとなる。
# よって、以下が答え
# (行の全体の選び方 - '1'のある行を１つも含めない選び方) * 列の全体の選び方 / 2

n, m = map(int, input().split())
MOD = 998244353
rows = []
for line in sys.stdin:
    b = ''.join(line.rstrip().split())
    rows.append(int(b, base=2))

independent_row = 0
while rows:
    x = max(rows)
    if x == 0:
        break
    independent_row += 1
    y = 1 << (x.bit_length() - 1)
    rows = [r ^ x if r & y else r for r in rows if r != x]

ans = (pow(2, n + m - 1, MOD) - pow(2, n + m - independent_row - 1, MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
# MOD = 10 ** 9 + 7
MOD = 998244353

N, M = list(map(int, sys.stdin.readline().split()))
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 列を選んだときに 1 が 1 個でもあれば奇数になるように選べるのが 2^(N-1) 通り
# 0 個になる数を数えて引く

# 方程式とく
A = np.array(A, dtype=int)
A = np.hstack((A, [[0] for _ in range(N)])).astype(bool)
rank = 0
for col in range(M):
    if rank >= N:
        break
    row = A[rank:, col].argmax() + rank
    if not A[row, col]:
        continue
    pivot_row = A[row].copy()
    A[A[:, col]] ^= pivot_row
    A[row] = A[rank]
    A[rank] = pivot_row
    rank += 1

# 1が1つ以上ある列の選び方
col_count = pow(2, M, MOD) - pow(2, M - rank, MOD)
# 1が1つ以上ある列から行の選び方が 2^(N-1) ある
ans = col_count * pow(2, N - 1, MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
列ベクトルが M 個ある
いくつかを選ぶ（和をとる）→すべての行が0となる選び方：0、その他：2^{N-1}通り
列ベクトル空間の生成する次元：d次元
ans = 2^{N-1} * (2^M - 2^[M-d})
= 2^{N+M-1} * (1-2^{-rank})
"""

import numpy as np
MOD = 998244353
N,M = map(int,input().split())
A = np.array([[int(x) for x in input().split()] for _ in range(N)])

def rank(A):
    # F_2 上の行列のrank
    N,M = A.shape
    if N == 0 or M == 0:
        return 0
    nz = np.nonzero(A[0])[0]
    if len(nz) == 0:
        # first col = zero
        return rank(A[1:])
    i = nz[0]
    # swap
    temp = A[:,i].copy()
    A[:,i] = A[:,0]
    A[:,0] = temp
    # (0,0) 成分が 1 になった。行基本変形。
    A ^= A[0][None,:] * A[:,0][:,None]
    return 1 + rank(A[1:,1:])

d = rank(A)
answer = pow(2,N+M-1,MOD) * (1 - pow(2,(-d)%(MOD-1), MOD)) % MOD
print(answer)

Submission status: Accepted

Solution code:
class GE():
    #mod2　なら　Aは1重リストで渡して, max(bit_length) をMに渡してあげた方が速い
    def __init__(self, A, mod, M = 0):
        self.N = len(A)
        if M:
            self.M = M
        else:
            self.M = len(A[0])
        self.mod = mod
        self.A = A[:]
        self.uptri = None
        self.A2 = None
        self.pivot = []
        self.R = None
    def ut(self):
        if self.mod != 2:
            if self.uptri is not None:
                return self.uptri
            self.uptri = self.A[:]
            c = 0
            for i in range(self.N):
                if i + c >= self.M:
                    break
                while self.uptri[i][i+c] == 0:
                    for j in range(i+1, self.N):
                        if self.uptri[j][i+c]:
                            self.uptri[i], self.uptri[j] = self.uptri[j], self.uptri[i]
                            break
                    else:
                        c += 1
                        if i + c == self.M:
                            break
                else:
                    self.pivot.append((i, i+c))
                    t = pow(self.uptri[i][i+c], self.mod - 2, self.mod)
                    for j in range(i+1, self.N):
                        tj = t * self.uptri[j][i+c]
                        self.uptri[j][i+c:] = [(aj - tj*ai) % self.mod for ai, aj in zip(self.uptri[i][i+c:], self.uptri[j][i+c:])]
                    continue
                break
            for pi, pj in self.pivot[::-1]:
                t = pow(self.uptri[pi][pj], self.mod-2, self.mod)
                self.uptri[pi][pj:] = [(ai * t) % self.mod for ai in self.uptri[pi][pj:]]
                for i in range(pi-1, -1, -1):
                    ti = self.uptri[i][pj]
                    self.uptri[i][pj:] = [(ai - api*ti) % self.mod for ai, api in zip(self.uptri[i][pj:], self.uptri[pi][pj:])]
            
            return self.uptri
        else:
            if self.A2 is not None:
                return self.A2
            self.A2 = self.A[:]
            c = 0
            for i in range(self.N):
                if i + c >= self.M:
                    break
                while not self.A2[i] & 2**(i+c):
                    for j in range(i+1, self.N):
                        if self.A2[j] & 2**(i+c):
                            self.A2[i], self.A2[j] = self.A2[j], self.A2[i]
                            break
                    else:
                        c += 1
                        if i + c == self.M:
                            break
                else:
                    self.pivot.append((i, i+c))
                    for j in range(i+1, self.N):
                        if self.A2[j] & 2**(i+c):
                            self.A2[j] ^= self.A2[i]
                    continue
                break
            for pi, pj in self.pivot[::-1]:
                for i in range(pi-1, -1, -1):
                    if 2**pj & self.A2[i]:
                        self.A2[i] ^= self.A2[pi]
            
            return self.A2
            
                
    def rank(self):
        if self.R is not None:
            return self.R
        self.ut()
        self.R = len(self.pivot)
        return self.R

N, M = map(int, input().split())
A = [sum(2**i for i, v in enumerate(map(int, input().split())) if v == 1)  for _ in range(N)]
mod = 998244353
T = GE(A, 2, M)
print((pow(2, N+M-1, mod) - pow(2, N+M-T.rank()-1, mod)) % mod)

Submission status: Accepted

Solution code:
class GE():
    def __init__(self, A, mod):
        self.N = len(A)
        self.M = len(A[0])
        self.A = A[:]
        self.mod = mod
        self.uptri = None
        self.pivot = []
        self.R = None
    def ut(self):
        if self.uptri is not None:
            return self.uptri
        self.uptri = self.A[:]
        
        c = 0
        for i in range(self.N):
            if i + c >= self.M:
                break
            while self.uptri[i][i+c] == 0:
                for j in range(i+1, self.N):
                    if self.uptri[j][i+c]:
                        self.uptri[i], self.uptri[j] = self.uptri[j], self.uptri[i]
                        break
                else:
                    c += 1
                    if i + c == self.M:
                        return self.uptri
            self.pivot.append((i, i+c))
            t = pow(self.uptri[i][i+c], self.mod - 2, self.mod)
            for j in range(i+1, self.N):
                tj = t * self.uptri[j][i+c]
                self.uptri[j][i+c:] = [(aj - tj*ai) % self.mod for ai, aj in zip(self.uptri[i][i+c:], self.uptri[j][i+c:])]
        for pi, pj in self.pivot[::-1]:
            t = pow(self.uptri[pi][pj], self.mod-2, self.mod)
            self.uptri[pi][pj:] = [(ai * t) % self.mod for ai in self.uptri[pi][pj:]]
            for i in range(pi-1, -1, -1):
                ti = self.uptri[i][pj]
                self.uptri[i][pj:] = [(ai - api*ti) % self.mod for ai, api in zip(self.uptri[i][pj:], self.uptri[pi][pj:])]
        
        return self.uptri
    def rank(self):
        if self.R is not None:
            return self.R
        self.ut()
        self.R = len(self.pivot)
        return self.R
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
mod = 998244353
T = GE(A, 2)
print((pow(2, N+M-1, mod) - pow(2, N+M-T.rank()-1, mod)) % mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A
"""
n,k = LI()
if 2*(k-1) < n:
    print("YES")
else:
    print("NO")
"""

#B
"""
c = LIR(3)
v = [[] for i in range(4)]
for i in range(3):
    c[i][0] -= 1
    c[i][1] -= 1
    v[c[i][0]].append(c[i][1])
    v[c[i][1]].append(c[i][0])

for i in range(4):
    li = [True for i in range(4)]
    li[i] = False
    q = [i]
    c = 0
    while q:
        x = q.pop(-1)
        k = 0
        for j in v[x]:
            if li[j]:
                li[j] = False
                q.append(j)
                if k == 0:
                    c += 1
                    k += 1
    if c == 3:
        print("YES")
        quit()
print("NO")
"""

#C
"""
k,a,b = LI()
if k <= a:
    print(k+1)
else:
    if b-a < 3:
        print(k+1)
    else:
        ans = a+((k-a+1)//2)*(b-a)+(k-a+1)%2
        print(ans)
"""

#D

#E
n,m = LI()
a = LIR(n)
a.sort()
a = a[::-1]
for i in range(n):
    for j in range(i+1,n):
        s = 0
        while a[i][s] == 0 and s < m-1:s+=1
        if s < m and a[i][s] != 0:
            if a[j][s] > 0:
                for k in range(s,m):
                    a[j][k] -= 1*a[i][k]
                    a[j][k] = abs(a[j][k])
r = 0
for i in range(n):
    if sum(a[i]) > 0:r += 1
print((pow(2,n+m-1)-pow(2,n-r+m-1))%998244353)
#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
import numpy as np
import random

mod=998244353


n,m=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]

#n,m=300,300
#A=[[int(random.randint(0,1)) for j in range(m)] for i in range(n)]


#A=np.array(A)

#print("A")
i=0
j=0
r=0 #rank
while i<n and j<m :
    #print(i)
    t=0
    if A[i][j]==0 :
        k=i
        while k<n and A[k][j]==0 :
            k+=1
        if k<n :
            A[i],A[k]=A[k],A[i]

            #print(A)
        else :
            t=1
            j+=1
    if t==0 :
        r+=1
        for p in range(i+1,n):
            if A[p][j]>0 :
                for kk in range(j,m):
                    A[p][kk]=(A[p][kk]-A[i][kk])%2
        i+=1
        j+=1



#r=0
#j=0
#for i in range(m):
#    if j<n :
#        if A[j][i]!=0 :
#            r+=1
#            j+=1

for i in range(n):
    for j in range(m):
        A[i][j]=int(A[i][j])
#print(A)
#print(r) #rank

a=1
b=1

for i in range(n+m-1):
    a=(a*2)%mod
for i in range(n+m-1-r):
    b=(b*2)%mod

print((a-b)%mod)

Submission status: Accepted

Solution code:
import numpy as np
mod = 998244353
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

#F2で考えている
def rank(a):
    n, m = len(a), len(a[0])
    rank = 0
    i, j = 0, 0
    while i < n and j < m:
        if a[i][j]:
            rank += 1
        else:
            for ii in range(i+1, n):
                if a[ii][j]:
                    a[i], a[ii] = a[ii], a[i]
                    rank += 1
                    break

            #breakで終わらなかった場合
            else:
                j += 1
                continue
        for ii in range(i+1, n):
            if a[ii][j]:
                for jj in range(j, m):
                    a[ii][jj] = (a[ii][jj] + a[i][jj])%2
        i += 1
        j += 1

    return rank

r = rank(a)
ans = (pow(2, n+m-1, mod)-pow(2, n+m-r-1, mod))%mod
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[[int(i) for i in input().split()] for i in range(N)]
r=0
mod=998244353
for j in range(M):
  flag=False
  for i in range(r,N):
    if not flag:
      if A[i][j]:
        flag=True
        A[i],A[r]=A[r],A[i]
        r+=1
    else:
      if A[i][j]:
        for k in range(M):
          A[i][k]^=A[r-1][k]

Factorial=[1]*(r+1)
for i in range(1,r+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod
  
inverseFactorial=[1]*(r+1)
inverseFactorial[r]=power(Factorial[r],mod-2)
for i in range(0,r)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

ans=0
a=1
while a<=r:
  ans=(ans+comb(r,a)*power(3,r-a)*power(4,min(N,M)-r)*power(2,max(N,M)-min(N,M)))%mod
  a+=2
print(ans)

Submission status: Accepted

Solution code:
def rankmod2(A):
    n,m=len(A),len(A[0])
    rank=0
    i,j=0,0
    while i<n and j<m:
        if A[i][j]:
            rank+=1
        else:
            for ii in range(i+1,n):
                if A[ii][j]:
                    A[i],A[ii]=A[ii],A[i]
                    rank+=1
                    break
            else:
                j+=1
                continue
        for ii in range(i+1,n):
            if A[ii][j]:
                for jj in range(j,m):
                    A[ii][jj]=(A[ii][jj]+A[i][jj])% 2
        i+=1
        j+=1
    return rank

n,m=map(int,input().split())
mod=998244353
A=[list(map(int,input().split())) for _ in range(n)]
r=rankmod2(A)
ans=(pow(2,n+m-1,mod)-pow(2,n+m-r-1,mod))%mod
print(ans)

Submission status: Accepted

Solution code:
def rankmod2(A):
    global N, M
    ret = 0
    i = 0
    j = 0
    while i < N and j < M:
        if A[i][j]:
            ret += 1
        else:
            for ii in range(i+1, N):
                if A[ii][j]:
                    A[i], A[ii] = A[ii], A[i]
                    ret += 1
                    break
            else:
                j += 1
                continue
                
        for ii in range(i+1, N):
            if A[ii][j]:
                for jj in range(j, M):
                    A[ii][jj] = (A[ii][jj] + A[i][jj]) % 2
        i += 1
        j += 1
        
    return ret
                        
P = 998244353
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
r = rankmod2(A)
print((pow(2, N+M-1, P)-pow(2, N+M-r-1, P)) % P)

Submission status: Accepted

Solution code:
def intmod2(n):
    return int(n) % 2

def rankmod2(A):
    global N, M
    ret = 0
    i = 0
    j = 0
    while i < N and j < M:
        if A[i][j]:
            ret += 1
        else:
            for ii in range(i+1, N):
                if A[ii][j]:
                    A[i], A[ii] = A[ii], A[i]
                    ret += 1
                    break
            else:
                j += 1
                continue
                
        for ii in range(i+1, N):
            if A[ii][j]:
                for jj in range(j, M):
                    A[ii][jj] = (A[ii][jj] + A[i][jj]) % 2
        i += 1
        j += 1
        
    return ret
                        
P = 998244353
N, M = map(int, input().split())
A = [list(map(intmod2, input().split())) for _ in range(N)]
r = rankmod2(A)
print((pow(2, N+M-1, P)-pow(2, N+M-r-1, P)) % P)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [long(input_raw[0]), long(input_raw[1])]
    A = []
    A_str = []
    for i in range(N):
        input_raw = read_func().strip().split()
        A_str.append(input_raw)
    is_all_zero_set = set([])
    for i in range(M):
        is_all_zero = True
        for j in range(N):
            if A_str[j][i] != "0":
                is_all_zero = False
                break
        if is_all_zero == True:
            is_all_zero_set.add(i)


    for i in range(N):
        col = -1
        a = 0
        for j in range(M):
            if j in is_all_zero_set:
                continue
            col += 1
            a += int(A_str[i][j]) << col
        A.append(a)
    M_new = col + 1
##    is_set = set([])
##    is_all_zero_set = set([])
##    A_ = [0 for i in range(N)]
##    all_zero_count = 0

##    for i in range(max(M, N)):
##        is_all_zero = True
##        for j in range(N):
##            if (A[j] & (0x01 << i)) > 0 and j not in is_set:
##                A_[i] = A[j]
##                is_set.add(j)
##                break

##    for i in range(max(M, N)):
##        is_all_zero = True
##        for j in range(N):
##            if (A[j] & (0x01 << i)) > 0:
##                is_all_zero =False
##            if (A[j] & (0x01 << i)) > 0 and j not in is_set:
##                A_[i] = A[j]
##                is_set.add(j)
##                is_all_zero =False
##                break
##        if is_all_zero == True:
##            is_all_zero_set.add(i)
##            all_zero_count += 1
##            for j in range(N):
##                if j not in is_set:
##                    A_[i] = A[j]
##                    is_set.add(j)
##                    break

    for i in range(min(N, M_new)):
        if (A[i] >> i) & 0x01 == 0:
            for j in range(i + 1, N):
                if (A[j] >> i) & 0x01 > 0:
                    tmp = A[j]
                    A[j] = A[i]
                    A[i] = tmp

        for j in range(N):
            if j == i:
                continue
            if ((A[j] >> i) & 0x01) > 0:
                A[j] = A[j] ^ A[i]
    r = 0
    for i in range(N):
        if A[i] != 0:
            r += 1
    k = N - min(r, M_new)
    count1 = 1L
    for i in range(M-1):
        count1 = (count1 * 2L)%998244353
    count2 = 1L
    for i in range(N):
        count2 = (count2 * 2L)%998244353
    count3 = 1L
    for i in range(k):
        count3 = (count3 * 2L)%998244353
    count = (count1 * ((count2 - count3) %998244353))%998244353
    print count



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

mod = 998244353

for i in range(n):
    for j in range(m):
        a[i][j] = a[i][j] % 2

# 掃き出し法
rank = 0
for i in range(n):
    target = -1
    for j in range(rank, m):
        if a[i][j]:
            target = j
            break

    if target == -1:
        continue

    if target != rank:
        for k in range(rank, n):
            a[k][rank], a[k][target] = a[k][target], a[k][rank]

    for k in range(i+1, n):
        if a[k][rank]:
            for j in range(m):
                a[k][j] ^= a[i][j]

    rank += 1


def modpow(a, n, mod=mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

print(modpow(2, m-1) * (modpow(2, n) - modpow(2, n-rank)) % mod)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 998244353
n, m = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in [0]*n])
if n > m:
	a = a.T
	n, m = m, n
#a[:, [0, 1]] = a[:, [1, 0]]
#print(a)
r = 0
for i in range(n):
	if a[i][i] != 1:
		for j in range(i+1, m):
			if a[i][j] == 1:
				a[:, [i, j]] = a[:, [j, i]]
				break
		else:
			for j in range(i+1, n):
				if a[j][i] == 1:
					a[[i, j]] = a[[j, i]]
				break
			else:
				break
	if a[i][i] == 0:
		continue

	r += 1
	for j in range(i+1, m):
		a[:, j] += a[i][j] * a[:, i]
		a[:, j] %= 2
	for j in range(i+1, n):
		a[j] += a[j][i] * a[i]
		a[j] %= 2
#print(r)
print((pow(2, n+m-1, MOD) - pow(2, n+m-r-1, MOD)) % MOD)

Submission status: Accepted

Solution code:
# from : https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4212377
H,W = map(int, input().split())
A = [ [int(j) for j in input().split()] for _ in range(H)]
MOD = 998244353

piv = 0

# Gaussian Elimination to calculate rank of the matrix A
for w in range(W): # fix column, 
    r = -1
    for h in range(piv, H):
        if A[h][w] == 1:
            r = h
            break
    if r == -1: # there is no odd cell for all the rows inside intersections.
        continue 

    # You want to set ODD ROW ( A[h][w] == 1 ) into pivot row.
    if r != piv: # already, skip.
        for j in range(W): # swap rows
            A[r][j], A[piv][j] = A[piv][j], A[r][j]

    # for h in 
    for h in range(H):
        if h != piv and A[h][w] == 1: # really needed?
            # for j in range(W):
            for k in range(piv, W):
                A[h][k] ^= A[piv][k]
                # A[h][j] ^= A[piv][j] # for other rows, erase ...
                # Hakidashi method: http://senkei.nomaki.jp/gaussian_elimination.html
                # https://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E3%81%AE%E6%B6%88%E5%8E%BB%E6%B3%95 : Gaussian Elimination
    piv += 1


# print("----output matrix ----")
# for h in range(H):
#     print(A[h])
# exit(0)


# from pprint import pprint; pprint(A)

ret = 1
ret = pow(2, H, MOD)
# for h in range(H):
#     ret = ret * 2 % MOD

sub = 1
# for i in range(H-piv):
#     sub = sub * 2 % MOD
sub = pow(2, H-piv, MOD)


ret += MOD - sub          # ret = 2^N - 2^(N-r)
ret %= MOD

for i in range(W-1):      # ret *= 2^(M-1)
    ret = ret * 2 % MOD

# from editorial  : https://img.atcoder.jp/yahoo-procon2019-qual/editorial.pdf
# rank : r 
# 2^(N+M-1) - 2^(N+M-r-1)

print(ret % MOD)