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:
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 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:
		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:
		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:
		if (decided[n*i+i+2] + decided[n*i+i+n+1] + decided[n*i+i+2*n]) % 2 != 0:
			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

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:
	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:
	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(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mod = 998244353
print(pow(2, (N ** 2 - M) // 2))

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_d

インラインdpを習得したから再挑戦
2*2→3*3…と塗っていくと、毎回2個を決めることとなる

新たに塗る2箇所をどう決められるかを考える
→偶奇を反転させる場合、01 or 10で塗り、させない場合は11 or 00で塗る
→1箇所までなら塗られていても自由度が下がるだけ？
→両方塗られていたらまずい場合がある

基本的に4列目以降は00 01の対以外不可能になる
→すでに片側置かれていたら1択、両側でダメだったら0になる
→つまり、考えるべきは3列目までである

3列目までは、片側は問題ないが、両側は制約として作動する
1列目(i=j)は文字を確定させる
2列目(abs(i-j)!=1)は隣り合う文字が同じ or 異なるを確定させる
3列目は、1列目の文字を確定させる

"""

from sys import stdin
import sys
mod = 998244353

N,M = map(int,stdin.readline().split())

neq = {}
eq = [None] * N
lock = [None] * (N-1)

for loop in range(M):

    a,b,c = map(int,stdin.readline().split())
    a -= 1
    b -= 1
    if a < b:
        a,b = b,a
    
    if a == b:
        if eq[a] == None or eq[a] == c:
            eq[a] = c
        else:
            print (0)
            sys.exit()
    
    elif a-b == 1:
        if (a,b) in neq:
            lock[b] = (neq[(a,b)] ^ c)
        else:
            neq[(a,b)] = c

    elif a-b == 2:
        if (a,b) in neq:
            if eq[a-1] == None or eq[a-1] == neq[(a,b)]^c:
                eq[a-1] = neq[(a,b)]^c
            else:
                print (0)
                sys.exit()
        else:
            neq[(a,b)] = c

    else:
        if (a,b) in neq:
            if neq[(a,b)] ^ c == 1:
                print (0)
                sys.exit()
        else:
            neq[(a,b)] = c

ableout = (N**2-N)//2 - len(neq)
outans = pow(2,ableout,mod)

dp = [[0,0] for i in range(N)]
dp[0] = [1,1]

for i in range(N):

    if eq[i] == 0:
        dp[i][1] = 0
    if eq[i] == 1:
        dp[i][0] = 0

    if i == N-1:
        break

    if lock[i] == 0:
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
    elif lock[i] == 1:
        dp[i+1][0] = dp[i][1]
        dp[i+1][1] = dp[i][0]
    else:
        dp[i+1][0] = sum(dp[i]) % mod
        dp[i+1][1] = sum(dp[i]) % mod

#print (dp , ableout)
print (sum(dp[-1]) * outans % mod)

Submission status: Accepted

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:
                jj.add((min(vn, vf), max(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: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・適当な部分空間なので、達成可能でありさえすれば数え上げは簡単
・対角成分に関して向かい側はまとめる。「必ず0」「必ず1」「free」
・対角から遠いところについては調整不可能。「必ず1」がここにあると死亡
・そうでない場合、対角～対角+2までを矛盾なく作れれば勝ち
"""

import itertools

MOD = 998244353

N,M = map(int,readline().split())
m = map(int,read().split())
ABC = list(zip(m,m,m))

# ある：10点
from collections import defaultdict
counter = defaultdict(int)
for a,b,c in ABC:
    if a>b:
        a,b = b,a
    counter[(a,b)] += 10+c

diag0 = [-1] * N
diag1 = [-1] * N # 後ろに足す
diag2 = [-1] * N # 前後に足す
free = N*(N-1)//2 # （盤面に対して対角ごとの和をとったもの）ごとの自由度
other = []
for (x,y),n in counter.items():
    if x>y:
        x,y = y,x
    d = y-x
    if d == 0:
        diag0[x-1] = n-10
        continue
    n = -1 if n<20 else n&1 # 未確定(-1) or 確定(0,1)
    if d >= 3:
        other.append(n)
    elif d == 1:
        diag1[x-1] = n
    elif d == 2:
        diag2[x-1] = n
    else:
        raise Exception

if 1 in other:
    print(0)
    exit()

for i,x in enumerate(diag2[:-2]):
    if x == -1:
        continue
    y = diag0[i+1]
    if y == -1:
        diag0[i+1] = x # 対角成分が強制される
        continue
    # どちらも強制されている
    if x != y:
        print(0)
        exit()

"""
diag0, diag1 の状態を元に、完成図の通り数を数える。
列ごとに処理。対角成分に書き込まれるのが、0のときa通り、1のときb通り
"""

if diag0[0] == -1:
    dp = [1,1]
elif diag0[0] == 0:
    dp = [1,0]
else:
    dp = [0,1]
for x0,x1 in zip(diag0[1:],diag1[:-1]):
    it0 = ([0],[1],[0,1])[x0]
    it1 = ([0],[1],[0,1])[x1]
    prev = dp
    dp = [0,0]
    for y0,y1 in itertools.product(it0,it1):
        dp[y0] += prev[y0^y1]
    if dp[0] > MOD: dp[0] -= MOD
    if dp[1] > MOD: dp[1] -= MOD

x = dp[0] + dp[1] # 完成盤面+transepose(完成盤面)が何通りあるか

# あとは、指定状態を固定したときの自由度
free = N*(N-1)//2
for (r,c),n in counter.items():
    if r == c:
        continue
    if n >= 10:
        free -= 1

answer = x * pow(2,free,MOD) % MOD
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
MOD = 998244353
n, m = map(int, input().split())
d = Counter()
ans = 1
d_num = 0
def k(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())
	d[(a-1)*n+b-1] = c
	if abs(a-b) >= 3:
		if (b-1)*n+a-1 not in d:
			d_num += 1
			d[(b-1)*n+a-1] = c
		elif d[(b-1)*n+a-1] != d[(a-1)*n+b-1]:
			print(0)
			sys.exit()
ans = (ans*k(2, ((n-2)*(n-3)//2)-d_num))%MOD
e = 0
if 0 not in d:
	e+=1
if 1 not in d:
	e+=1
if n not in d:
	e+=1
if n+1 not in d:
	e+=1
if e == 0 and n*0+0 in d:
	if (d[n*0+0]+d[n+1])%2!=(d[1]+d[n]) % 2:
		ans *= 0
if e == 1 and n+1 not in d and n*0+0 in d:
	d[n+1] = (d[1]+d[n])%2-d[n*0+0]
ans = (ans*(2**max(0, e-1))) % MOD
for i in range(n-2):
	e = 0
	if n*i+i+2 not in d:
		e += 1
	if n*i+i+2*n not in d:
		e += 1
	if e == 0 and n*i+i+n+1 in d:
		if (d[n*i+i+2] + d[n*i+i+n+1] + d[n*i+i+2*n]) % 2 != 0:
			ans *= 0
	if e == 0 and n*i+i+n+1 not in d:
		d[n*i+i+n+1] = (d[n*i+i+2] + d[n*i+i+n*2]) % 2
		ans = (ans*499122177) % MOD
	ans = (ans*(2 ** max(0, e-1))) % MOD
	e=0
	if n*(i+1)+i+2 not in d:
		e += 1
	if n*(i+1)+i+1+n not in d:
		e += 1
	if n*(i+1)+i+n+2 not in d:
		e += 1
	if e == 0 and n*(i+1)+i+1 in d:
		if (d[n*(i+1)+i+1]+d[n*(i+1)+i+n+2]) % 2 != (d[n*(i+1)+i+2]+d[n*(i+1)+i+1+n])%2:
			ans *= 0
	if e == 0 and n*(i+1)+i+1 not in d:
		ans = (ans*499122177) % MOD
	if e == 1 and n*(i+1)+i+2+n not in d and n*(i+1)+i+1 in d:
		d[n*(i+1)+i+2+n]=(d[n*(i+1)+i+2]+d[n*(i+1)+i+1+n])%2-d[n*(i+1)+i+1]
	ans = (ans*(2**max(0, e-1))) % MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
MOD = 998244353
n, m = map(int, input().split())
d = 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())
	d[(a-1) * n + b - 1] = c
	if abs(a-b) >= 3:
		if (b-1) * n + a - 1 not in d:
			d_num += 1
			d[(b-1) * n + a - 1] = c
		elif d[(b-1) * n + a - 1] != d[(a-1) * n + b - 1]:
			print(0)
			sys.exit()
ans = (ans * kaijou(2, ((n-2) * (n-3) // 2) - d_num)) % MOD
e = 0
if 0 not in d:
	e += 1
if 1 not in d:
	e += 1
if n not in d:
	e += 1
if n+1 not in d:
	e += 1
if e == 0 and n*0+0 in d:
	if (d[n*0+0] + d[n+1]) % 2 != (d[1] + d[n]) % 2:
		ans *= 0
if e == 1 and n+1 not in d and n*0+0 in d:
	d[n+1] = (d[1] + d[n]) % 2 - d[n*0+0]
ans = (ans * (2 ** max(0, e-1))) % MOD
for i in range(n-2):
	e = 0
	if n*i+i+2 not in d:
		e += 1
	if n*i+i+2*n not in d:
		e += 1
	if e == 0 and n*i+i+n+1 in d:
		if (d[n*i+i+2] + d[n*i+i+n+1] + d[n*i+i+2*n]) % 2 != 0:
			ans *= 0
	if e == 0 and n*i+i+n+1 not in d:
		d[n*i+i+n+1] = (d[n*i+i+2] + d[n*i+i+n*2]) % 2
		ans = (ans * 499122177) % MOD
	ans = (ans * (2 ** max(0, e-1))) % MOD
	e = 0
	if n*(i+1)+i+2 not in d:
		e += 1
	if n*(i+1)+i+1+n not in d:
		e += 1
	if n*(i+1)+i+n+2 not in d:
		e += 1
	if e == 0 and n*(i+1)+i+1 in d:
		if (d[n*(i+1)+i+1] + d[n*(i+1)+i+n+2]) % 2 != (d[n*(i+1)+i+2] + d[n*(i+1)+i+1+n]) % 2:
			ans *= 0
	if e == 0 and n*(i+1)+i+1 not in d:
		ans = (ans * 499122177) % MOD
	if e == 1 and n*(i+1)+i+2+n not in d and n*(i+1)+i+1 in d:
		d[n*(i+1)+i+2+n] = (d[n*(i+1)+i+2] + d[n*(i+1)+i+1+n]) % 2 - d[n*(i+1)+i+1]
	ans = (ans * (2 ** max(0, e-1))) % MOD
print(ans)

Submission status: Accepted

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

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.bit =[0]*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]
            self.bit[gy]=max(self.bit[gy],self.bit[gx])
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            self.bit[gx]=max(self.bit[gy],self.bit[gx])

    def freeze(self,x,b):
        r=self.find_root(x)
        self.bit[r]=1

    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={}
freeze=[-1]*(N+1)
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)
        if freeze[a]==-1:
            freeze[a]=c
        elif freeze[a]!=c:
            print(0)
            exit()
    elif a==b+1:
        if connect[b]!=-1:
            uf.unite(b-1,a-1)
            connect[b]=(c+connect[b])%2
        else:
            connect[b]=c
            co-=1
    elif a==b+2:
        id=(a+b)//2
        if decide[id]!=-1:
            check=(decide[id]+c)%2
            uf.freeze(id-1,check)
            if freeze[id]==-1:
                freeze[id]=check
            elif freeze[id]!=check:
                print(0)
                exit()
        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)

for i in range(1,N):
    if connect[i]!=-1:
        if freeze[i]==-1 or freeze[i+1]==-1:
            continue
        elif (freeze[i]+freeze[i+1]+connect[i])%2==1:
            print(0)
            exit()

diag=set([])
for i in range(N):
    r=uf.find_root(i)
    if uf.get_bit(r)==0:
        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: Runtime Error

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)
    
    assert len(jj) == 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: Runtime Error

Solution code:
from collections import defaultdict
Q = 998244353
D = defaultdict( int)
N, M = map( int, input().split())
L = (N**2-N)//2
Ld = N
ans = 1
diag = [-1]*(N+1)
A = [(0,0,0)]*M
for _ in range(M):
    a, b, c = map( int, input().split())
    if a == b:
        D[(a,b)] = c+2
        Ld -= 1
    else:
        L -= 1
        D[(a,b)] = c+2
for i in range(N-1):
    if D[(i,i)] >= 2 and D[(i,i+1)] >= 2 and D[(i+1,i)] >= 2 and D[(i+1,i+1)] >= 2:
        if not (D[(i,i)] + D[(i,i+1)] + D[(i+1,i)] + D[(i+1,i+1)])%2 == 0:
            ans = 0
print( ans*pow(2,L+Ld,Q))

Submission status: Runtime Error

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


# 可能かどうかの判定
def f(A):
    return True


if f(A):
    free = N * (N + 1) // 2 - M
    print(pow(2, free, mod))
else:
    print(0)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().strip().split(' '))
assert M == 0
print(pow(2, (N ** 2 - N * (N - 1) // 2), 998244353))