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: Runtime Error

Solution code:
N,M=map(int,input().split());mod=998244353;B=[]
for i in range(N):
    s=int(input().split().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: Runtime Error

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
ans = pow(2,n+m-2*cnt,mod)*pow(2,cnt-1,mod)*(pow(2,cnt,mod)-1)%mod
print(ans)

Submission status: Runtime Error

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):
  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
ans = pow(2,n+m-2*cnt,mod)*pow(2,cnt-1,mod)*(pow(2,cnt,mod)-1)%mod
print(ans)

Submission status: Runtime Error

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] * A[:,0]
    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: Runtime Error

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:
            if a[j][s] > 0:
                d = a[j][s]/a[i][s]
                for k in range(s,m):
                    a[j][k] -= d*a[i][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))
#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Runtime Error

Solution code:
import numpy as np

mod=998244353


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

A.sort(reverse=1)
A=np.array(A)

# if A[0][0]!=0

#print(A)
for i in range(min(n,m)):
    #print(A)
    A=list(A)
    A[i:].sort(reverse=1,key=lambda x:x[i])
    if A[i][i]==0 :
        A[i:].sort(key=lambda x:x[i])
    A=np.array(A)
    if A[i][i]!=0 :
        w=A[i][i]
        for k in range(m):
            
            A[i][k]/=w
        for j in range(i+1,n):
            A[j]-=A[i]*A[j][i]

#print(A)

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

for i in range(n):
    for i 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: Runtime Error

Solution code:
import numpy as np

mod=998244353


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

A.sort(reverse=1)
A=np.array(A)

# if A[0][0]!=0

#print(A)
for i in range(min(n,m)):
    #print(A)
    A=list(A)
    A[i:].sort(reverse=1,key=lambda x:x[i])
    if A[i][i]==0 :
        A[i:].sort(key=lambda x:x[i])
    A=np.array(A)
    if A[i][i]!=0 :
        w=A[i][i]
        for k in range(m):
            
            A[i][k]/=w
        for j in range(i+1,n):
            A[j]-=A[i]*A[j][i]

#print(A)

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

for i in range(n):
    for i 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: Runtime Error

Solution code:
import numpy as np

mod=998244353


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

A.sort(reverse=1)
A=np.array(A)

# if A[0][0]!=0

#print(A)
for i in range(min(n,m)):
    #print(A)
    A=list(A)
    A[i:].sort(reverse=1,key=lambda x:x[i])
    A=np.array(A)
    if A[i][i]!=0 :
        w=A[i][i]
        for k in range(m):
            
            A[i][k]/=w
        for j in range(i+1,n):
            A[j]-=A[i]*A[j][i]

#print(A)

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

#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: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define rep2(i,k,n) for(int i=k;i>=n;i--)
#define mod 998244353
using namespace std;
inline void upd(int& x,int y){
	x+=y;
	x-= (x>mod) ? mod : 0;
}
const int N=305;
int pw[N<<1],f[N],a[N][N],n,m;
int main(){
	pw[0]=1;rep(i,1,600)pw[i]=pw[i-1],upd(pw[i],pw[i-1]);
	rep(i,1,N-1)f[i]=pw[(i-1)<<1],upd(f[i],f[i-1]),upd(f[i],f[i-1]);
	scanf("%d%d",&n,&m);
	rep(i,1,n)rep(j,1,m)scanf("%d",&a[i][j]);
	int r=0;
	rep(i,1,n){
		int t=0;
		rep(j,i,n)if(a[j][i]){t=j;break;}
		if(!t)continue;
		r++;
		rep(j,1,m)swap(a[i][j],a[t][j]);
		rep(j,i+1,n)if(a[j][i]){
			rep(k,i,m)a[j][k]^=a[i][k];
		}
	}
	int ans=1ll*f[r]*pw[n-r]%mod*pw[m-r]%mod;
	printf("%d\n",ans);
}

Submission status: Runtime Error

Solution code:
N,M=map(int, raw_input().split())
A=[ map(int, raw_input().split()) for i in range(N) ]

if N>M:  N,M=M,N

for k in range(N): #k: pivot
	if A[k][k]==0 and max(A[k])==1:
		for i in range(N):
			if A[i][k]==1:
				#Gyou koukan
				A[k],A[i] = A[i],A[k]
				break

	for i in range(N):
		if i!=k and A[i][k]==1:
			for j in range(M):
				A[i][j]+=A[k][j]
				A[i][j]%=2

r=0 #Rank

s=set()
for x in A:
	t=""
	if max(x)!=0:
		for i in x:
			t+=str(i)
		s.add(t)

r=len(s)


p=998244353

print ( pow(2,N+M-1,p)-pow(2,N+M-r-1,p) )%p

Submission status: Runtime Error

Solution code:
import numpy as np
IN()=lambda:list(map(int,input().split()))
n,m=IN()
a=np.array([IN() for i in range(n)])
r=np.linalg.matrix_rank(a)
print((2**(n+m-1)-2**(n+m-1-r))%998244353)

Submission status: Runtime Error

Solution code:
import numpy as np
IN()=lambda:list(map(int,input().split()))
n,m=IN()
a=np.array([IN() for i in range(n)])
r=np.np.linalg.matrix_rank(a)
print((2**(n+m-1)-2**(n+m-1-r))%998244353)

Submission status: Runtime Error

Solution code:
N,M=map(int, raw_input().split())
A=[ map(int, raw_input().split()) for i in range(N) ]

if N>M:  N,M=M,N

for k in range(N): #k: pivot
	if A[k][k]==0 and max(A[k])==1:
		for i in range(N):
			if A[i][k]==1:
				#Gyou koukan
				A[k],A[i] = A[i],A[k]
				break

	for i in range(N):
		if i!=k and A[i][k]==1:
			for j in range(M):
				A[i][j]+=A[k][j]
				A[i][j]%=2

r=0 #Rank

for x in A:
	if max(x)!=0: r+=1


p=998244353

print ( pow(2,N+M-1,p)-pow(2,N+M-r-1,p) )%p

Submission status: Runtime Error

Solution code:
N,M=map(int, raw_input().split())
A=[ map(int, raw_input().split()) for i in range(N) ]

if N>M:  N,M=M,N

for k in range(N): #k: pivot
	if A[k][k]==0:
		for i in range(N):
			if A[i][k]==1:
				#Gyou koukan
				A[k],A[i] = A[i],A[k]
				break

	for i in range(N):
		if i!=k and A[i][k]==1:
			for j in range(M):
				A[i][j]+=A[k][j]
				A[i][j]%=2

r=0 #Rank

for x in A:
	if max(x)!=0: r+=1


p=998244353

print ( pow(2,N+M-1,p)-pow(2,N+M-r-1,p) )%p

Submission status: Runtime Error

Solution code:
N,M=map(int, raw_input().split())
A=[ map(int, raw_input().split()) for i in range(N) ]

if N>M: N,M=M,N

for k in range(N):	#k: pivot
	if A[k][k]==0:
		for i in range(N):
			if A[i][k]==1:
				#Gyou koukan
				for j in range(M):
					A[k][j],A[i][j] = A[i][j],A[k][j]
				break

	for i in range(N):
		if i!=k and A[i][k]==1:
			for j in range(M):
				A[i][j]+=A[i-1][j]
				A[i][j]%=2


r=0 #Rank

for x in A:
	if max(x)!=0: r+=1


p=998244353

print ( pow(2,N+M-1,p)-pow(2,N+M-r-1,p) )%p

Submission status: Runtime Error

Solution code:
N,M=map(int, raw_input().split())
A=[ map(int, raw_input().split()) for i in range(N) ] 

for k in range(N):	#k: pivot

	if A[k][k]==0:
		for i in range(N):
			if A[i][k]==1:
				#Gyou koukan
				for j in range(M):
					A[k][j],A[i][j] = A[i][j],A[k][j]
				break

	for i in range(N):
		if i!=k:
			for j in range(M):	#retsu
				if A[i][k]==1:
					for j in range(M):
						A[i][j]+=A[i-1][j]
						A[i][j]%=2


r=0 #Rank

for x in A:
	if max(x)!=0: r+=1


p=998244353

print ( pow(2,N+M-1,p)-pow(2,N+M-r-1,p) )%p

Submission status: Runtime Error

Solution code:
import numpy as np
 
N,M=map(int, input().split())
A=[ list( map(int, input().split()) ) for i in range(N) ] 
 
R=np.linalg.matrix_rank(A)
 
print ( (2**N - 2**(N-R) )*2**(M-1) )

Submission status: Runtime Error

Solution code:
import numpy as np

N,M=map(int, raw_input().split())
A=np.array( [ map(int, raw_input().split()) for i in range(N) ] )

R=np.linalg.matrix_rank(A)

print (2**N - 2**(N-R) )*2**(M-1)

Submission status: Runtime Error

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 = []
    for i in range(N):
        input_raw = read_func().strip().split()
        a = 0
        for j in range(M):
            a += int(input_raw[j]) << j
        A.append(a)
    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:
                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

    row = -1
    for i in range(min(N, M)):
        if i in is_all_zero_set:
            continue
        row += 1
        for j in range(row+1, N):
            if ((A_[j] >> i) & 0x01) > 0:
                A_[j] = A_[j] ^ A_[row]
    r = 0
    for i in range(N):
        if A_[i] != 0:
            r += 1
    k = N - min(r, M - all_zero_count)
    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: Runtime Error

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 = []
    for i in range(N):
        input_raw = read_func().strip().split()
        a = 0
        for j in range(M):
            a += int(input_raw[j]) << j
        A.append(a)
    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:
                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

    row = -1
    for i in range(min(N, M)):
        if i in is_all_zero_set:
            continue
        row += 1
        for j in range(row+1, N):
            if ((A_[j] >> row) & 0x01) > 0:
                A_[j] = A_[j] ^ A_[row]
    r = 0
    for i in range(N):
        if A_[i] != 0:
            r += 1
    k = N - min(r, M - all_zero_count)
    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: Runtime Error

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])
#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: Runtime Error

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])
#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: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
aij = np.zeros((N,M),dtype=int)
for i in range(M):
  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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
if os.environ.get("USER") == "shun":
    def debug(*args): print(*args, file=sys.stderr)
else:
    print("NO DEBUG", file=sys.stderr)
    def debug(*args): pass
def exit(): sys.exit(0)


l = int(input())
a = []
for _ in range(l):
    a.append(int(input()))

init_score = 0
for i in range(l):
    if a[i] == 0:
        init_score += 2
    elif a[i] % 2 == 0:
        pass
    else:
        init_score += 1

left = [0]
for i in range(l):
    left.append(left[i])
    if a[i] == 0:
        left[i+1] -= 2
    elif a[i] % 2 == 0:
        left[i+1] += a[i]
    else:
        left[i+1] += a[i] - 1
left_i = 0
left_min = left[0]
for i in range(l+1):
    if left[i] < left_min:
        left_i = i
        left_min = left[i]
debug(left_i, left)

right = [0] * (l+1)
for i in range(l, 0, -1):
    right[i-1] = right[i]
    if a[i-1] == 0:
        right[i-1] -= 2
    elif a[i-1] % 2 == 0:
        right[i-1] += a[i-1]
    else:
        right[i-1] += a[i-1] - 1
right_i = 0
right_min = right[0]
for i in range(l+1):
    if right[i] < right_min:
        right_i = i
        right_min = right[i]
debug(right_i, right)


# odd
temp_score = init_score + left_min + right_min
b = a[left_i:right_i]
k = len(b)

for i in range(k):
    if b[i] == 0:
        temp_score -= 1
    elif b[i] % 2 == 0:
        temp_score += 1
    else:
        temp_score -= 1


left = [0]
for i in range(k):
    left.append(left[i])
    if b[i] == 0:
        left[i+1] += 1
    elif b[i] % 2 == 0:
        left[i+1] -= 1
    else:
        left[i+1] += 1
left_i = 0
left_min = left[0]
for i in range(k+1):
    if left[i] < left_min:
        left_i = i
        left_min = left[i]
debug(left_i, left)

right = [0] * (k+1)
for i in range(k, 0, -1):
    right[i-1] = right[i]
    if b[i-1] == 0:
        right[i-1] += 1
    elif b[i-1] % 2 == 0:
        right[i-1] -= 1
    else:
        right[i-1] += 1
right_i = 0
right_min = right[0]
for i in range(k+1):
    if right[i] < right_min:
        right_i = i
        right_min = right[i]
debug(right_i, right)

score = temp_score + left_min + right_min
print(score)