Problem:


Score : 900 points

Problem Statement

Takahashi has an N \times N grid. The square at the i-th row and the j-th column of the grid is denoted by (i,j).
Particularly, the top-left square of the grid is (1,1), and the bottom-right square is (N,N).

An integer, 0 or 1, is written on M of the squares in the Takahashi's grid.
Three integers a_i,b_i and c_i describe the i-th of those squares with integers written on them: the integer c_i is written on the square (a_i,b_i).

Takahashi decides to write an integer, 0 or 1, on each of the remaining squares so that the condition below is satisfied.
Find the number of such ways to write integers, modulo 998244353.

For all 1\leq i < j\leq N, there are even number of 1s in the square region whose top-left square is (i,i) and whose bottom-right square is (j,j).

Constraints

2 \leq N \leq 10^5

0 \leq M \leq min(5 \times 10^4,N^2)

1 \leq a_i,b_i \leq N(1\leq i\leq M)

0 \leq c_i \leq 1(1\leq i\leq M)

If i \neq j, then (a_i,b_i) \neq (a_j,b_j).

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1 c_1
:
a_M b_M c_M

Output

Print the number of possible ways to write integers, modulo 998244353.

Sample Input 1

3 3
1 1 1
3 1 0
2 3 1

Sample Output 1

8

For example, the following ways to write integers satisfy the condition:

101   111
011   111
000   011

Sample Input 2

4 5
1 3 1
2 4 0
2 3 1
4 2 1
4 4 1

Sample Output 2

32

Sample Input 3

3 5
1 3 1
3 3 0
3 1 0
2 3 1
3 2 1

Sample Output 3

0

Sample Input 4

4 8
1 1 1
1 2 0
3 2 1
1 4 0
2 1 1
1 3 0
3 4 1
4 4 1

Sample Output 4

4

Sample Input 5

100000 0

Sample Output 5

342016343



Sample input:
3 3
1 1 1
3 1 0
2 3 1


Sample output:
8

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
mod = 998244353

factorial=[1 for i in range(2*N+1)]
for i in range(1,2*N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i % mod

def comb(n,k):
    return (factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod))%mod

memo=[[0]*2 for _ in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  memo[max(a,b)-1][c] += 1
  
ans = 0
for i in range(N-1,0,-1):
  tmp = 0
  n_margin = 2*(i+1)-1-sum(memo[i])
  if (memo[i][1] - memo[i-1][1]) % 2:
    if memo[i][1] % 2:
      for j in range(0,n_margin+1,2):
        tmp += comb(n_margin,j)
    else:
      for j in range(1,n_margin+1,2):
        tmp += comb(n_margin,j)
  else:
    if memo[i][1] % 2:
      for j in range(1,n_margin+1,2):
        tmp += comb(n_margin,j)
    else:
      for j in range(0,n_margin+1,2):
        tmp += comb(n_margin,j)
  print(i,n_margin,tmp,sum(memo[i]))
  ans += tmp
  ans %= mod
  
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.bit=[-1]*N
        self.ans=1

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            if self.bit[gy]==-1:
                self.bit[gy]=self.bit[gx]
            elif self.bit[gx]!=-1 and self.bit[gx]!=self.bit[gy]:
                self.ans=0
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            if self.bit[gx]==-1:
                self.bit[gx]=self.bit[gy]
            elif self.bit[gy]!=-1 and self.bit[gy]!=self.bit[gx]:
                self.ans=0

    def freeze(self,x,b):
        r=self.find_root(x)
        if self.bit[r]==-1:
            self.bit[r]=b
        elif self.bit[r]!=b:
            self.ans=0

    def get_bit(self,x):
        return self.bit[self.find_root(x)]

    def get_ans(self):
        return self.ans

    def in_ans(self,x):
        self.ans=x

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.buffer.readline

N,M=map(int,input().split())
free=(N-3)*(N-2)//2
co=N-1
t=N-2
connect=[-1]*(N+1)
decide=[-1]*(N+1)
freedic={}
uf=UnionFindVerSize(N)
for i in range(M):
    a,b,c=map(int,input().split())
    if b>a:
        a,b=b,a
    if a==b:
        uf.freeze(a-1,c)
    elif a==b+1:
        if connect[b]==1:
            uf.unite(b-1,a-1)
        else:
            connect[b]=1
            co-=1
    elif a==b+2:
        id=(a+b)//2
        if decide[id]!=-1:
            check=(decide[id]+c)%2
            uf.freeze(id-1,check)
        else:
            decide[id]=c
            t-=1
    else:
        if (a,b) not in freedic:
            freedic[(a,b)]=0
            freedic[(a,b)]=c
            free-=1
        else:
            if freedic[(a,b)]!=c:
                uf.in_ans(0)

diag=set([])
for i in range(N):
    r=uf.find_root(i)
    if uf.get_bit(r)==-1:
        diag.add(uf.find_root(i))

dddd=len(diag)
mod=998244353
print(pow(2,free+co+t+dddd,mod)*uf.get_ans())
#print(free)
#print(co)
#print(t)
#print(dddd)

Submission status: Wrong Answer

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.bit=[-1]*N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            if self.bit[gy]==-1:
                self.bit[gy]=self.bit[gx]
            elif self.bit[gx]!=-1 and self.bit[gx]!=self.bit[gy]:
                print(0)
                exit()
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            if self.bit[gx]==-1:
                self.bit[gx]=self.bit[gy]
            elif self.bit[gy]!=-1 and self.bit[gy]!=self.bit[gx]:
                print(0)
                exit()

    def freeze(self,x,b):
        r=self.find_root(x)
        if self.bit[r]==-1:
            self.bit[r]=b
        elif self.bit[r]!=b:
            print(0)
            exit()

    def get_bit(self,x):
        return self.bit[self.find_root(x)]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.buffer.readline

N,M=map(int,input().split())
free=(N-3)*(N-2)//2
co=N-1
t=N-2
connect=[-1]*(N+1)
decide=[-1]*(N+1)
freedic={}
uf=UnionFindVerSize(N)
for i in range(M):
    a,b,c=map(int,input().split())
    if b>a:
        a,b=b,a
    if a==b:
        uf.freeze(a-1,c)
    elif a==b+1:
        if connect[b]==1:
            uf.unite(b-1,a-1)
        else:
            connect[b]=1
            co-=1
    elif a==b+2:
        id=(a+b)//2
        if decide[id]!=-1:
            check=(decide[id]+c)%2
            uf.freeze(id-1,check)
        else:
            decide[id]=c
            t-=1
    else:
        if (a,b) not in freedic:
            freedic[(a,b)]=0
            freedic[(a,b)]=c
            free-=1
        else:
            if freedic[(a,b)]!=c:
                print(0)
                exit()

diag=set([])
for i in range(N):
    r=uf.find_root(i)
    if uf.get_bit(r)==-1:
        diag.add(uf.find_root(i))

dddd=len(diag)
mod=998244353
print(pow(2,free+co+t+dddd,mod))
#print(free)
#print(co)
#print(t)
#print(dddd)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, defaultdict, deque
readline = sys.stdin.readline

MOD = 998244353
def calc():
    N, M = map(int, readline().split())
    D = Counter()
    Grid = defaultdict(lambda: -1)
    flag = True
    geta = N
    co = 0
    for _ in range(M):
        a, b, c = map(int, readline().split())
        a -= 1
        b -= 1
        
        if abs(b - a) >= 3:
            if a > b:
                a, b = b, a
            if (a, b) in D:
                if D[(a, b)] != c:
                    flag = False
            else:
                D[(a, b)] = c
                co += 1
        else:
            Grid[a*geta+b] = c
    
    if not flag:
        return 0
        
    for i in range(N-2):
        g = Grid[(i+1)*geta+(i+1)]
        g1 = Grid[i*geta+(i+2)]
        g2 = Grid[(i+2)*geta+i]
        if g1 == -1 or g2 == -1:
            continue
        if g != -1:
            if (g1 == g2) == g:
                return 0
        else:
            Grid[(i+1)*geta+(i+1)] = int(g1 != g2)
    

    
    Edge = [[] for _ in range(N)]
    for i in range(N-1):
        g1 = Grid[(i+1)*geta+i]
        g2 = Grid[i*geta+(i+1)]
        if g1 == -1 or g2 == -1:
            continue
        
        k = int(g1 != g2)
        Edge[i].append((i+1, k))
        Edge[i+1].append((i, k))
    
    Diag = [None]*N
    Q = []
    for i in range(N):
        if Grid[i*geta+i] != -1:
            Diag[i] = Grid[i*geta+i]
            Q.append(i)
    
    
    Q = deque(Q)
    while Q:
        vn = Q.pop()
        for vf, k in Edge[vn]:
            if Diag[vf] is None:
                Diag[vf] = k^Diag[vn]
                Q.appendleft(vf)
            else:
                if Diag[vf] != k^Diag[vn]:
                    return 0
    
    jj = set()
    for vn in range(N):
        for vf, k in Edge[vn]:
            if Diag[vn] is None:
                if vn > vf:
                    vn, vf = vf, vn
                jj.add((vn, vf))
    
    co += len(jj)
    
    if len(jj) > 0:
        return 0
    
    co += N - Diag.count(None)
    used = set()
    
    for i in range(N-1):
        if Grid[i*geta + (i+1)] != -1:
            used.add((i, i+1))
        if Grid[(i+1)*geta + i] != -1:
            used.add((i, i+1))
    
    for i in range(N-2):
        if Grid[i*geta + (i+2)] != -1:
            used.add((i, i+2))
        if Grid[(i+2)*geta + i] != -1:
            used.add((i, i+2))
    
    co += len(used)
    return pow(2, N*(N+1)//2 - co, MOD)

print(calc())

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, defaultdict, deque
readline = sys.stdin.readline

MOD = 998244353
def calc():
    N, M = map(int, readline().split())
    D = Counter()
    Grid = defaultdict(lambda: -1)
    flag = True
    geta = N
    co = 0
    for _ in range(M):
        a, b, c = map(int, readline().split())
        a -= 1
        b -= 1
        
        if abs(b - a) >= 3:
            if a > b:
                a, b = b, a
            if (a, b) in D:
                if D[(a, b)] != c:
                    flag = False
            else:
                D[(a, b)] = c
                co += 1
        else:
            Grid[a*geta+b] = c
    
    if not flag:
        return 0
        
    for i in range(N-2):
        g = Grid[(i+1)*geta+(i+1)]
        g1 = Grid[i*geta+(i+2)]
        g2 = Grid[(i+2)*geta+i]
        if g1 == -1 or g2 == -1:
            continue
        if g != -1:
            if (g1 == g2) == g:
                return 0
        else:
            Grid[(i+1)*geta+(i+1)] = int(g1 != g2)
    

    
    Edge = [[] for _ in range(N)]
    for i in range(N-1):
        g1 = Grid[(i+1)*geta+i]
        g2 = Grid[i*geta+(i+1)]
        if g1 == -1 or g2 == -1:
            continue
        
        k = int(g1 != g2)
        Edge[i].append((i+1, k))
        Edge[i+1].append((i, k))
    
    Diag = [None]*N
    Q = []
    for i in range(N):
        if Grid[i*geta+i] != -1:
            Diag[i] = Grid[i*geta+i]
            Q.append(i)
    
    
    Q = deque(Q)
    while Q:
        vn = Q.pop()
        for vf, k in Edge[vn]:
            if Diag[vf] is None:
                Diag[vf] = k^Diag[vn]
                Q.appendleft(vf)
            else:
                if Diag[vf] != k^Diag[vn]:
                    return 0
    
    jj = set()
    for vn in range(N):
        for vf, k in Edge[vn]:
            if Diag[vn] is None:
                if vn > vf:
                    vn, vf = vf, vn
                jj.add((vn, vf))
    
    co += len(jj)
    
    co += N - Diag.count(None)
    used = set()
    
    for i in range(N-1):
        if Grid[i*geta + (i+1)] != -1:
            used.add((i, i+1))
        if Grid[(i+1)*geta + i] != -1:
            used.add((i, i+1))
    
    for i in range(N-2):
        if Grid[i*geta + (i+2)] != -1:
            used.add((i, i+2))
        if Grid[(i+2)*geta + i] != -1:
            used.add((i, i+2))
    
    co += len(used)
    return pow(2, N*(N+1)//2 - co, MOD)

print(calc())

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, defaultdict, deque
readline = sys.stdin.readline

MOD = 998244353
def calc():
    N, M = map(int, readline().split())
    D = Counter()
    Grid = defaultdict(lambda: -1)
    flag = True
    geta = N
    co = 0
    for _ in range(M):
        a, b, c = map(int, readline().split())
        a -= 1
        b -= 1
        
        if abs(b - a) >= 3:
            if a > b:
                a, b = b, a
            if (a, b) in D:
                if D[(a, b)] != c:
                    flag = False
            else:
                D[(a, b)] = c
                co += 1
        else:
            Grid[a*geta+b] = c
    
    if not flag:
        return 0
        
    for i in range(1, N-1):
        g = Grid[i*geta+i]
        g1 = Grid[(i+1)*geta+i-1]
        g2 = Grid[(i-1)*geta+i+1]
        if g1 == -1 or g2 == -1:
            continue
        if g != -1:
            if (g1 == g2) == g:
                return 0
        else:
            Grid[i*geta+i] = int(g1 != g2)
    

    
    Edge = [[] for _ in range(N)]
    for i in range(N-1):
        g1 = Grid[(i+1)*geta+i]
        g2 = Grid[i*geta+i+1]
        if g1 == -1 or g2 == -1:
            continue
        
        k = int(g1 != g2)
        Edge[i].append((i+1, k))
        Edge[i+1].append((i, k))
    
    Diag = [None]*N
    Q = []
    for i in range(N):
        if Grid[i*geta+i] != -1:
            Diag[i] = Grid[i*geta+i]
            Q.append(i)
    
    
    Q = deque(Q)
    
    
    while Q:
        vn = Q.pop()
        for vf, k in Edge[vn]:
            if Diag[vf] is None:
                Diag[vf] = k^Diag[vn]
                Q.appendleft(vf)
            else:
                if Diag[vf] != k^Diag[vn]:
                    return 0
    
    co += N - Diag.count(None)
    used = set()
    
    for i in range(N-1):
        if Grid[i*geta + i+1] != -1:
            used.add((i, i+1))
        if Grid[(i+1)*geta + i] != -1:
            used.add((i, i+1))
    
    for i in range(N-2):
        if Grid[i*geta + i+2] != -1:
            used.add((i, i+2))
        if Grid[(i+2)*geta + i] != -1:
            used.add((i, i+2))
    
    co += len(used)
    return pow(2, N*(N+1)//2 - co, MOD)

print(calc())

Submission status: Wrong Answer

Solution code:
MOD = 998244353
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x: min(x[0], x[1]))
p = [[] for _ in range(n)]
even = [2] * n
odd = [2] * n
t = [i - 1 for i in range(n)]
k = [1] * n
q = [1] * n
for a, b, c in l:
    a -= 1
    b -= 1
    a, b = min(a, b), max(a, b)
    if p[b] and (p[b][-1] >> 1) == a:
        cc = p[b][-1] & 1
        if b - a >= 2 and cc != c:
            k[b] = 0
            if b - a >= 3:
                q[b] = 0
        elif b - a == 2 and cc == c:
            q[b] = 0
        elif b - a == 1:
            if cc == c:
                odd[b] = 0
            else:
                even[b] = 0

    elif b - a >= 2:
        t[b] -= 1
    p[b].append(a * 2 + c)
    if a == b:
        continue
    if b - a == 1:
        even[b] = min(even[b], 1)
        odd[b] = min(odd[b], 1)
dp = [[0] * n for _ in range(2)]
dp[0][0] = 1
dp[1][0] = 1
for i, l in enumerate(p[:-1]):
    if l and (l[-1] >> 1) == i:
        dp[~(l[-1] & 1)][i] = 0
    dp[0][i + 1] += dp[0][i] * \
        pow(2, t[i + 1], MOD) * even[i + 1] * k[i + 1] % MOD
    dp[0][i + 1] += dp[1][i] * \
        pow(2, t[i + 1], MOD) * odd[i + 1] * k[i + 1] % MOD
    dp[1][i + 1] += dp[0][i] * \
        pow(2, t[i + 1], MOD) * odd[i + 1] * k[i + 1] % MOD
    dp[1][i + 1] += dp[1][i] * \
        pow(2, t[i + 1], MOD) * even[i + 1] * q[i + 1] % MOD
if p[-1] and (p[-1][-1] >> 1) == n - 1:
    dp[(p[-1][-1] & 1) ^ 1][n - 1] = 0
print((dp[0][-1] + dp[1][-1]) % MOD)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x: min(x[0], x[1]))
p = [[] for _ in range(n)]
even = [2] * n
odd = [2] * n
cnt = [2 * i for i in range(n)]
t = [i - 1 for i in range(n)]
k = [1] * n
q = [1] * n
for a, b, c in l:
    a -= 1
    b -= 1
    a, b = min(a, b), max(a, b)
    if p[b] and (p[b][-1] >> 1) == a:
        cc = p[b][-1] & 1
        if b - a >= 3 and cc != c:
            q[b] = 0
            k[b] = 0
        elif b - a == 2:
            k[b] = 0
        elif b - a == 1:
            if cc == c:
                odd[b] = 0
            else:
                even[b] = 0

    elif b - a >= 2:
        t[b] -= 1
    p[b].append(a * 2 + c)
    if a == b:
        continue
    cnt[b] -= 1
    if b - a == 1:
        even[b] = min(even[b], 1)
        odd[b] = min(odd[b], 1)
dp = [[0] * n for _ in range(2)]
dp[0][0] = 1
dp[1][0] = 1
for i, l in enumerate(p[:-1]):
    if l and (l[-1] >> 1) == i:
        dp[~(l[-1] & 1)][i] = 0
    dp[0][i + 1] += dp[0][i] * \
        pow(2, t[i + 1], MOD) * even[i + 1] * k[i + 1] % MOD
    dp[0][i + 1] += dp[1][i] * \
        pow(2, t[i + 1], MOD) * odd[i + 1] * k[i + 1] % MOD
    dp[1][i + 1] += dp[0][i] * \
        pow(2, t[i + 1], MOD) * odd[i + 1] * k[i + 1] % MOD
    dp[1][i + 1] += dp[1][i] * \
        pow(2, t[i + 1], MOD) * even[i + 1] * q[i + 1] % MOD
if p[-1] and (p[-1][-1] >> 1) == n - 1:
    dp[(p[-1][-1] & 1) ^ 1][n - 1] = 0
print((dp[0][-1] + dp[1][-1]) % MOD)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
MOD = 998244353
n, m = map(int, input().split())
decided = Counter()
ans = 1
d_num = 0

def kaijou(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = (x * a) % MOD
		a = (a ** 2) % MOD
		n >>= 1
	return x

for _ in range(m):
	a, b, c = map(int, input().split())
	decided[(a-1) * n + b - 1] = c
	if abs(a-b) >= 3:
		if (b-1) * n + a - 1 not in decided:
			d_num += 1
			ans = (ans * 2) % MOD
			decided[(b-1) * n + a - 1] = c
		elif decided[(b-1) * n + a - 1] != decided[(a-1) * n + b - 1]:
			print(0)
			sys.exit()

ans = (ans * kaijou(2, ((n-2) * (n-3) // 2) - d_num)) % MOD
#print(ans)

is_empty = 0

if n*0+0 not in decided:
	is_empty += 1
if n*0+0+1 not in decided:
	is_empty += 1
if n*0+0+n not in decided:
	is_empty += 1
if n*0+0+n+1 not in decided:
	is_empty += 1

if is_empty == 0 and n*0+0 in decided:
	if (decided[n*0+0] + decided[n*0+0+n+1]) % 2 != (decided[n*0+0+1] + decided[n*0+0+n]) % 2:
		ans *= 0

if is_empty == 1 and n*0+0+n+1 not in decided and n*0+0 in decided:
	decided[n*0+0+n+1] = (decided[n*0+0+1] + decided[n*0+0+n]) % 2 - decided[n*0+0]

ans = (ans * (2 ** max(0, is_empty-1))) % MOD

#print(ans)
for i in range(n-2):

	is_empty = 0
	#if n*i+i+n+1 not in decided:
		#is_empty += 1
	if n*i+i+2 not in decided:
		is_empty += 1
	if n*i+i+2*n not in decided:
		is_empty += 1

	if is_empty == 0 and n*i+i+n+1 in decided:
		if (decided[n*i+i+2] + decided[n*i+i+n+1] + decided[n*i+i+2*n]) % 2 != 0:
			#print("hoge")
			ans *= 0

	if is_empty == 0 and n*i+i+n+1 not in decided:
		decided[n*i+i+n+1] = (decided[n*i+i+2] + decided[n*i+i+n*2]) % 2
		ans = (ans * 499122177) % MOD

	ans = (ans * (2 ** max(0, is_empty-1))) % MOD

	is_empty = 0

	if n*(i+1)+(i+1)+1 not in decided:
		is_empty += 1
	if n*(i+1)+(i+1)+n not in decided:
		is_empty += 1
	if n*(i+1)+(i+1)+n+1 not in decided:
		is_empty += 1

	if is_empty == 0 and n*(i+1)+(i+1) in decided:
		if (decided[n*(i+1)+(i+1)] + decided[n*(i+1)+(i+1)+n+1]) % 2 != (decided[n*(i+1)+(i+1)+1] + decided[n*(i+1)+(i+1)+n]) % 2:
			ans *= 0

	if is_empty == 0 and n*(i+1)+(i+1) not in decided:
		ans = (ans * 499122177) % MOD

	if is_empty == 1 and n*(i+1)+(i+1)+n+1 not in decided and n*(i+1)+(i+1) in decided:
		decided[n*(i+1)+(i+1)+n+1] = (decided[n*(i+1)+(i+1)+1] + decided[n*(i+1)+(i+1)+n]) % 2 - decided[n*(i+1)+(i+1)]

	ans = (ans * (2 ** max(0, is_empty-1))) % MOD


print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
MOD = 998244353
n, m = map(int, input().split())
decided = Counter()
ans = 1
d_num = 0

def kaijou(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = (x * a) % MOD
		a = (a ** 2) % MOD
		n >>= 1
	return x

for _ in range(m):
	a, b, c = map(int, input().split())
	decided[(a-1) * n + b - 1] = c
	if abs(a-b) >= 3:
		if (b-1) * n + a - 1 not in decided:
			d_num += 1
			ans = (ans * 2) % MOD
			decided[(b-1) * n + a - 1] = c
		elif decided[(b-1) * n + a - 1] != decided[(a-1) * n + b - 1]:
			print(0)
			sys.exit()

ans = (ans * kaijou(2, ((n-2) * (n-3) // 2) - d_num)) % MOD
#print(ans)

is_empty = 0

if n*0+0 not in decided:
	is_empty += 1
if n*0+0+1 not in decided:
	is_empty += 1
if n*0+0+n not in decided:
	is_empty += 1
if n*0+0+n+1 not in decided:
	is_empty += 1

if is_empty == 0 and n*0+0 in decided:
	if (decided[n*0+0] + decided[n*0+0+n+1]) % 2 != (decided[n*0+0+1] + decided[n*0+0+n]) % 2:
		ans *= 0

if is_empty == 1 and n*0+0+n+1 not in decided and n*0+0 in decided:
	decided[n*0+0+n+1] = (decided[n*0+0+1] + decided[n*0+0+n]) % 2 - decided[n*0+0]

ans = (ans * (2 ** max(0, is_empty-1))) % MOD

#print(ans)
for i in range(n-2):

	is_empty = 0
	#if n*i+i+n+1 not in decided:
		#is_empty += 1
	if n*i+i+2 not in decided:
		is_empty += 1
	if n*i+i+2*n not in decided:
		is_empty += 1

	if is_empty == 0 and n*i+i+n+1 in decided:
		if (decided[n*i+i+2] + decided[n*i+i+n+1] + decided[n*i+i+2*n]) % 2 != 0:
			#print("hoge")
			ans *= 0

	if is_empty == 0 and n*i+i+n+1 not in decided:
		decided[n*i+i+n+1] = (decided[n*i+i+2] + decided[n*i+i+n*2]) % 2

	ans = (ans * (2 ** max(0, is_empty-1))) % MOD

	is_empty = 0

	if n*(i+1)+(i+1)+1 not in decided:
		is_empty += 1
	if n*(i+1)+(i+1)+n not in decided:
		is_empty += 1
	if n*(i+1)+(i+1)+n+1 not in decided:
		is_empty += 1

	if is_empty == 0 and n*(i+1)+(i+1) in decided:
		if (decided[n*(i+1)+(i+1)] + decided[n*(i+1)+(i+1)+n+1]) % 2 != (decided[n*(i+1)+(i+1)+1] + decided[n*(i+1)+(i+1)+n]) % 2:
			ans *= 0

	if is_empty == 1 and n*(i+1)+(i+1)+n+1 not in decided and n*(i+1)+(i+1) in decided:
		decided[n*(i+1)+(i+1)+n+1] = (decided[n*(i+1)+(i+1)+1] + decided[n*(i+1)+(i+1)+n]) % 2 - decided[n*(i+1)+(i+1)]

	ans = (ans * (2 ** max(0, is_empty-1))) % MOD


print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
MOD = 998244353
n, m = map(int, input().split())
decided = Counter()
ans = 1
d_num = 0

def kaijou(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = (x * a) % MOD
		a = (a ** 2) % MOD
		n >>= 1
	return x

for _ in range(m):
	a, b, c = map(int, input().split())
	decided[(a-1) * n + b - 1] = c
	if abs(a-b) >= 3:
		if (b-1) * n + a - 1 not in decided:
			d_num += 1
			ans = (ans * 2) % MOD
			decided[(b-1) * n + a - 1] = c
		elif decided[(b-1) * n + a - 1] != decided[(a-1) * n + b - 1]:
			print(0)
			sys.exit()

ans = (ans * kaijou(2, ((n-2) * (n-3) // 2) - d_num)) % MOD


is_empty = 0

if n*0+0 not in decided:
	is_empty += 1
if n*0+0+1 not in decided:
	is_empty += 1
if n*0+0+n not in decided:
	is_empty += 1
if n*0+0+n+1 not in decided:
	is_empty += 1

if is_empty == 0 and n*0+0 in decided:
	if (decided[n*0+0] + decided[n*0+0+n+1]) % 2 != (decided[n*0+0+1] + decided[n*0+0+n]) % 2:
		ans *= 0

if is_empty == 1 and n*0+0+n+1 not in decided and n*0+0 in decided:
	decided[n*0+0+n+1] = (decided[n*0+0+1] + decided[n*0+0+n]) % 2 - decided[n*0+0]

ans = (ans * (2 ** max(0, is_empty-1))) % MOD

#print(ans)
for i in range(n-2):

	is_empty = 0
	#if n*i+i+n+1 not in decided:
		#is_empty += 1
	if n*i+i+2 not in decided:
		is_empty += 1
	if n*i+i+2*n not in decided:
		is_empty += 1

	if is_empty == 0 and n*i+i+n+1 in decided:
		if (decided[n*i+i+2] + decided[n*i+i+n+1] + decided[n*i+i+2*n]) % 2 != 0:
			#print("hoge")
			ans *= 0

	if is_empty == 0 and n*i+i+n+1 not in decided:
		decided[n*i+i+n+1] = (decided[n*i+i+2] + decided[n*i+i+n*2]) % 2

	ans = (ans * (2 ** min(0, is_empty-1))) % MOD

	is_empty = 0

	if n*(i+1)+(i+1)+1 not in decided:
		is_empty += 1
	if n*(i+1)+(i+1)+n not in decided:
		is_empty += 1
	if n*(i+1)+(i+1)+n+1 not in decided:
		is_empty += 1

	if is_empty == 0 and n*(i+1)+(i+1) in decided:
		if (decided[n*(i+1)+(i+1)] + decided[n*(i+1)+(i+1)+n+1]) % 2 != (decided[n*(i+1)+(i+1)+1] + decided[n*(i+1)+(i+1)+n]) % 2:
			ans *= 0

	if is_empty == 1 and n*(i+1)+(i+1)+n+1 not in decided and n*(i+1)+(i+1) in decided:
		decided[n*(i+1)+(i+1)+n+1] = (decided[n*(i+1)+(i+1)+1] + decided[n*(i+1)+(i+1)+n]) % 2 - decided[n*(i+1)+(i+1)]

	ans = (ans * (2 ** max(0, is_empty-1))) % MOD


print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
MOD = 998244353
n, m = map(int, input().split())
decided = Counter()
ans = 1
d_num = 0

def kaijou(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = (x * a) % MOD
		a = (a ** 2) % MOD
		n >>= 1
	return x

for _ in range(m):
	a, b, c = map(int, input().split())
	decided[(a-1) * n + b - 1] = c
	if abs(a-b) >= 3:
		if (b-1) * n + a - 1 not in decided:
			d_num += 1
			ans = (ans * 2) % MOD
			decided[(b-1) * n + a - 1] = c
		elif decided[(b-1) * n + a - 1] != decided[(a-1) * n + b - 1]:
			print(0)
			sys.exit()

ans = (ans * kaijou(2, ((n-2) * (n-3) // 2) - d_num)) % MOD

#print(ans)
for i in range(n-2):
	is_empty = 0

	if i == 0:
		if n*i+i not in decided:
			is_empty += 1
	if n*i+i+1 not in decided:
		is_empty += 1
	if n*i+i+n not in decided:
		is_empty += 1
	if n*i+i+n+1 not in decided:
		is_empty += 1

	if is_empty == 0 and n*i+i in decided:
		if (decided[n*i+i] + decided[n*i+i+n+1]) % 2 != (decided[n*i+i+1] + decided[n*i+i+n]) % 2:
			ans *= 0

	if is_empty == 1 and n*i+i+n+1 not in decided and n*i+i in decided:
		decided[n*i+i+n+1] = (decided[n*i+i+1] + decided[n*i+i+n]) % 2 - decided[n*i+i]

	ans = (ans * (2 ** max(0, is_empty-1))) % MOD

	is_empty = 0
	#if n*i+i+n+1 not in decided:
		#is_empty += 1
	if n*i+i+2 not in decided:
		is_empty += 1
	if n*i+i+2*n not in decided:
		is_empty += 1

	if is_empty == 0 and n*i+i+n+1 in decided:
		if (decided[n*i+i+2] + decided[n*i+i+n+1] + decided[n*i+i+2*n]) % 2 != 0:
			#print("hoge")
			ans *= 0

	if is_empty == 0 and n*i+i+n+1 not in decided:
		decided[n*i+i+n+1] = (decided[n*i+i+2] + decided[n*i+i+n*2]) % 2

	ans = (ans * (2 ** min(0, is_empty-1))) % MOD

#print(ans)
is_empty = 0
#if n*(n-2)+(n-2) not in decided:
	#is_empty += 1
if n*(n-2)+(n-2)+1 not in decided:
	is_empty += 1
if n*(n-2)+(n-2)+n not in decided:
	is_empty += 1
if n*(n-2)+(n-2)+n+1 not in decided:
	is_empty += 1

if is_empty == 0 and n*(n-2)+(n-2) in decided:
	if (decided[n*(n-2)+(n-2)] + decided[n*(n-2)+(n-2)+n+1]) % 2 != (decided[n*(n-2)+(n-2)+1] + decided[n*(n-2)+(n-2)+n]) % 2:
		ans *= 0

if is_empty == 1 and n*(n-2)+(n-2)+n+1 not in decided and n*(n-2)+(n-2) in decided:
	decided[n*(n-2)+(n-2)+n+1] = (decided[n*(n-2)+(n-2)+1] + decided[n*(n-2)+(n-2)+n]) % 2 - decided[n*(n-2)+(n-2)]

ans = (ans * (2 ** max(0, is_empty-1))) % MOD


print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
MOD = 998244353
n, m = map(int, input().split())
decided = Counter()
ans = 1
d_num = 0

def kaijou(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = (x * a) % MOD
		a = (a ** 2) % MOD
		n >>= 1
	return x

for _ in range(m):
	a, b, c = map(int, input().split())
	decided[(a-1) * n + b - 1] = c
	if abs(a-b) >= 3:
		if (b-1) * n + a - 1 not in decided:
			d_num += 1
			ans = (ans * 2) % MOD
			decided[(b-1) * n + a - 1] = c
		elif decided[(b-1) * n + a - 1] != decided[(a-1) * n + b - 1]:
			print(0)
			sys.exit()

ans = (ans * kaijou(2, ((n-2) * (n-3) // 2) - d_num)) % MOD

#print(ans)
for i in range(n-2):
	is_empty = 0

	if i == 0:
		if n*i+i not in decided:
			is_empty += 1
	if n*i+i+1 not in decided:
		is_empty += 1
	if n*i+i+n not in decided:
		is_empty += 1
	if n*i+i+n+1 not in decided:
		is_empty += 1

	if is_empty == 0 and n*i+i in decided:
		if (decided[n*i+i] + decided[n*i+i+n+1]) % 2 != (decided[n*i+i+1] + decided[n*i+i+n]) % 2:
			ans *= 0

	if is_empty == 1 and n*i+i+n+1 not in decided and n*i+i in decided:
		decided[n*i+i+n+1] = (decided[n*i+i+1] + decided[n*i+i+n]) % 2 - decided[n*i+i]

	ans = (ans * (2 ** max(0, is_empty-1))) % MOD

	is_empty = 0
	#if n*i+i+n+1 not in decided:
		#is_empty += 1
	if n*i+i+2 not in decided:
		is_empty += 1
	if n*i+i+2*n not in decided:
		is_empty += 1

	if is_empty == 0 and n*i+i+n+1 in decided:
		if (decided[n*i+i+2] + decided[n*i+i+n+1] + decided[n*i+i+2*n]) % 2 != 0:
			#print("hoge")
			ans *= 0

	if is_empty == 1 and n*i+i+n+1 not in decided :
		decided[n*i+i+n+1] = (decided[n*i+i+2] + decided[n*i+i+n*2]) % 2

	ans = (ans * (2 ** min(0, is_empty-1))) % MOD

#print(ans)
is_empty = 0
#if n*(n-2)+(n-2) not in decided:
	#is_empty += 1
if n*(n-2)+(n-2)+1 not in decided:
	is_empty += 1
if n*(n-2)+(n-2)+n not in decided:
	is_empty += 1
if n*(n-2)+(n-2)+n+1 not in decided:
	is_empty += 1

if is_empty == 0 and n*(n-2)+(n-2) in decided:
	if (decided[n*(n-2)+(n-2)] + decided[n*(n-2)+(n-2)+n+1]) % 2 != (decided[n*(n-2)+(n-2)+1] + decided[n*(n-2)+(n-2)+n]) % 2:
		ans *= 0

if is_empty == 1 and n*(n-2)+(n-2)+n+1 not in decided and n*(n-2)+(n-2) in decided:
	decided[n*(n-2)+(n-2)+n+1] = (decided[n*(n-2)+(n-2)+1] + decided[n*(n-2)+(n-2)+n]) % 2 - decided[n*(n-2)+(n-2)]

ans = (ans * (2 ** max(0, is_empty-1))) % MOD


print(int(ans))