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 1 s 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

Solution (Python):

"""

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 (sum(dp[-1]) * outans % mod)

Solution (Python):
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())

Solution (Python):
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))


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 
    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] 


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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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
			
			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


for i in range(n-2):

	is_empty = 0
	
		
	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:
			
			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))