実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 900 点
問題文
高橋君は、N 行 N 列のマス目を持っています。マス目の上から i 番目、左から j 番目のマスは (i,j) で表されます。 特に、マス目の左上のマスは (1,1) であり、右下のマスは (N,N) です。
高橋君の持っているマス目のうち M 個のマスには、0 または 1 の整数が書き込まれています。 整数が書き込まれたマスのうち i 番目のマスの情報は 3 つの整数 a_i,b_i,c_i で表され、マス (a_i,b_i) に整数 c_i が書き込まれていることを表します。
高橋君は、以下の条件を満たすように残りのマスに 0 または 1 の整数を書き込むことにしました。 書き込み方としてありうるものの個数を 998244353 で割ったあまりを求めてください。
- 任意の 1\leq i < j\leq N に対し、(i,i) を左上のマスとし (j,j) を右下のマスとするような正方形領域に書き込まれた 1 の個数が偶数である
制約
- 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)
- i \neq j ならば (a_i,b_i) \neq (a_j,b_j) である
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 c_1 : a_M b_M c_M
出力
書き込み方としてありうるものの個数を 998244353 で割ったあまりを出力せよ。
入力例 1
3 3 1 1 1 3 1 0 2 3 1
出力例 1
8
例えば、以下のような書き込み方が条件を満たします。
101 111 011 111 000 011
入力例 2
4 5 1 3 1 2 4 0 2 3 1 4 2 1 4 4 1
出力例 2
32
入力例 3
3 5 1 3 1 3 3 0 3 1 0 2 3 1 3 2 1
出力例 3
0
入力例 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
出力例 4
4
入力例 5
100000 0
出力例 5
342016343
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