CF40E Number Table <计数>

Posted on Symbols count in article: 1k Reading time ≈ 4 mins.

Problem

Number Table

Time  Limit:  2  seconds\mathrm{Time\;Limit:\;2\;seconds}
Memory  Limit:  216  megabytes\mathrm{Memory\;Limit:\;216\;megabytes}

Description

As it has been found out recently, all the Berland’s current economical state can be described using a simple table n×mn\times m in size. nn ― the number of days in each Berland month, mm ― the number of months. Thus, a table cell corresponds to a day and a month of the Berland’s year. Each cell will contain either 11, or −1-1, which means the state’s gains in a particular month, on a particular day. 11 corresponds to profits, −1-1 corresponds to losses. It turned out important for successful development to analyze the data on the state of the economy of the previous year, however when the treasurers referred to the archives to retrieve the data, it turned out that the table had been substantially damaged. In some table cells the number values had faded and were impossible to be deciphered. It is known that the number of cells in which the data had been preserved is strictly less than max⁡(n,m)\max(n,m). However, there is additional information ― the product of the numbers in each line and column equaled −1-1. Your task is to find out how many different tables may conform to the preserved data. As the answer to the task can be quite large, you have to find it modulo pp.

Input

The first line contains integers nn and mm (1≤n,m≤1000)(1\le n,m\le1000). The second line contains the integer kk (0≤k<max⁡(n,m))(0\le k<\max(n,m)) ― the number of cells in which the data had been preserved. The next kk lines contain the data on the state of the table in the preserved cells. Each line is of the form a b c, where aa (1≤a≤n)(1\le a\le n) ― the number of the table row, bb (1≤b≤m)(1\le b\le m) ― the number of the column, cc ― the value containing in the cell (11 or −1-1). They are numbered starting from 11. It is guaranteed that no two lines with same aa and bb values exist. The last line contains an integer pp (2≤p≤109+7)(2\le p\le10^9+7).

Output

Print the number of different tables that could conform to the preserved data modulo pp.

Example

Input #1

1
2
3
2 2
0
100

Output #1

1
2

Input #2

1
2
3
4
2 2
1
1 1 -1
100

Output #2

1
1

标签：计数

Translation

题目大意：有一个n×mn\times m的矩阵，其每个位置上的值为11或−1-1。已知其kk个位置的值，求有多少种填剩余位置的方案能使得其每行每列的乘积均为−1-1。输出答案模pp的值。

Solution

注意到重要的数据条件0≤k<max⁡(n,m)0\le k<\max(n,m)，可知其一定有一行或一列是不存在给定值的。如果m>nm>n，则交换行列，使得其一定剩一个空行。如果随意填除这一行外其他位置的值，保证其他行的乘积均为−1-1，一定能找到一种填这一行的方案使得所有列都是−1-1。这时，如果n,mn,m奇偶性相同，则这一行的乘积也为−1-1，符合所有条件；否则这一行的乘积一定为11，不存在可行解。因此，对于除这一行外的所有行统计每行乘积为−1-1的方案数相乘，再用n,mn,m奇偶性判断一下有无可行解即可。特别地，如果某一行全都有给定值，且乘积为11，则无解。
对于一个未填满给定值的行，选出第一个未填数的位置，对于其他空位随意填11或−1-1，如果填完后乘积为11，则第一个位置填−1-1，否则第一个位置填11。因此对于一个已填了cc个数的行，若c<mc<m，则其可行解种数为2m−c−12^{m-c-1}；若c=mc=m，如果乘积为11，则无可行解，否则有11种可行解。用乘法原理统计方案数即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define MAX_N 1000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m; bool f;
int c[MAX_N+5], w[MAX_N+5];
lnt P, pw[MAX_N+5], ans;
int main() {
    read(n), read(m); int T; read(T);
    if (n < m) swap(n, m), f = true;
    for (int i = 1; i <= n; i++) w[i] = 1;
    for (int x, y, v; T; T--) {
        read(x), read(y), read(v);
        if (f) swap(x, y);
        c[x]++, w[x] *= v;
    }
    read(P), pw[0] = 1;
    for (int i = 1; i <= m; i++)
        pw[i] = (pw[i-1]<<1)%P;
    for (int i = 1; i <= n; i++) if (!c[i])
        {swap(c[i], c[n]), swap(w[i], w[n]); break;}
    ans = ((n^m)&1) ? 0 : 1;		
    for (int i = 1; i < n; i++)
        if (c[i] == m && w[i] == 1) ans = 0;
        else if (c[i] < m) ans = ans*pw[m-c[i]-1]%P;
    return printf("%lld\n", ans), 0;
}