Skip to content

1046: 吹响!悠风号

题目

题目描述

音乐原本,并非为向对手炫耀自己的实力而存在的,然而现在在这里的众多其他学校的学生及观众,尚不了解北宇治的实力。所以老师认为,今天会是让大家领略我们实力的好机会,好了,去向大家展现我们北宇治的实力吧。

——《吹响!悠风号》

给你一个 $n$ 个行,$m$ 列的棋盘,每个位置都要填上 $1$ 或者 $-1$。其中有 $k$ 个位置以及填上了数,而其它的位置则等待你来填写。并且这个棋盘满足 $k$ 严格小于 $\max(n,m)$。

一个棋盘是和谐的,当且仅当每一行每一列乘积都是 $-1$。

求和谐的棋盘种类数,答案对 $p$ 取模。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每一组数据有以下输入:

第一行两个整数 $n,m$ 表示纸上是一个 $n\times m$ 的网格图。

第二行一个整数 $k$,表示已经有 $k$ 个位置填了数。

下面 $k$ 行,每行 $3$ 个正整数$x,y,c$,表示第 $x$ 行第 $y$ 列被填上了 $c$。保证没有重复位置出现。

接着一行一个整数 $p$。

输出格式

对于每组数据输出一个整数,表示方案数模 $p$ 后的结果。

样例输入

``` 2 2 2 1 1 1 -1 100 2 2 0 100

```

样例输出

``` 1 2

```

数据范围

对于 $30\%$ 的数据,保证$1\leq n\times m\leq 15$。

对于 $100\%$ 的数据,保证$1\leq n,m\leq 10^3$。

保证所有数据满足 $0\leq k\leq \max(n,m),c\in {-1,1},2\leq p\leq 10^9+7,1\leq T\leq 5$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!