#P5176. [Jsoi2013]优美矩阵

    ID: 4245 传统题 1000ms 512MiB 尝试: 15 已通过: 4 难度: 7 上传者: 标签>难度分类提高+/省选-线性代数与代数GF(2) 消元动态规划状态维度消除滚动数组秩判定模拟与实现技巧高精度加法CF2300

[Jsoi2013]优美矩阵

[JSOI2013] 优美矩阵

给定一个n*n的矩阵,矩阵中的每个数可能为1或-1。定义一种变换操作:矩阵中的每个数都变成变换前它上下左右四个数字的乘积(如果某个数上下左右某个位置没有数字,那就取其他数字的乘积)。 例如:

$$\begin{pmatrix} -1&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 \end{pmatrix} \longrightarrow \begin{pmatrix} 1&-1&1&1\\ -1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 \end{pmatrix}.$$

如果一个矩阵经过这样的变换操作后,得到的矩阵和原来的矩阵完全相同,那么我们称这样的矩阵是“优美”的。 (相同指对应位置的数字都相等,不考虑旋转或翻转后的相同。)现在,毛明明在一个空的矩阵中先选了若干个位置填上了数字,现在他想知道,如果把其他的位置都继续填满,最后得到的矩阵有多少种是“优美”的。

输入输出格式

输入格式

从标准输入读入。第一行两个整数 n,mn,m,分别表示矩阵大小和已填位置个数。 接下来m行,每行三个整数x、y、z,表示已在矩阵第x行、第y列填上了数字z。 (1<=x,y<=n,z为1或-1,且所有的x互不相同,所有的y互不相同。) N<=1000

输出格式

向标准输出写出一行一个整数,表示“优美”矩阵的个数(输出完整整数,无需取模)。 若不论怎么填都不能得到“优美”矩阵,则输出“0”。

样例

样例输入

4 2
1 1 -1
4 4 -1

样例输出

4

样例说明

四种满足样例条件的“优美”矩阵如下:

$$\begin{pmatrix} -1&1&1&1\\ -1&-1&1&1\\ -1&1&-1&1\\ 1&-1&-1&-1 \end{pmatrix},\qquad \begin{pmatrix} -1&1&1&-1\\ -1&-1&-1&-1\\ -1&-1&-1&-1\\ -1&1&1&-1 \end{pmatrix},$$$$\begin{pmatrix} -1&-1&-1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&1&1&-1 \end{pmatrix},\qquad \begin{pmatrix} -1&-1&-1&-1\\ 1&-1&-1&1\\ 1&-1&-1&1\\ -1&-1&-1&-1 \end{pmatrix}.$$