頁面無法載入？點擊這裡可能會修復。
Placeholder

#8162
子任務

전자 격자 1s 512MB

問題

매튜는 실리콘 기반의 N \times M 크기의 전자 격자를 연구하고 있다. 각 전자는 다음과 같은 두 가지 스핀 중 하나를 가진다:

  • + (positive): 위쪽 스핀

  • - (negative): 아래쪽 스핀

매튜는 다음 정보를 알고 있다:

  1. 일부 전자의 스핀 정보: K개의 측정을 통해 몇몇 전자의 스핀을 알고 있다.

  2. 2×2 서브그리드 조건: 모든 2×2 크기의 서브그리드에는 양의 스핀과 음의 스핀이 정확히 2개씩 있어야 한다.

매튜는 다음을 해결하려고 한다:

  1. 모든 전자의 스핀 상태를 유일하게 결정할 수 있는가?

  2. 그렇지 않다면, 그의 측정 결과와 위 조건을 만족하는 가능한 격자 상태의 개수를 10^9 + 7로 나눈 나머지를 계산해야 한다.


輸入

  • 첫 번째 줄: 세 개의 정수 N, M, K

    • N: 격자의 높이

    • M: 격자의 너비

    • K: 측정된 전자의 수

  • 다음 K개의 줄:

    • 각 줄은 스핀 s_i​ (+ 또는 -)와 두 정수 y_i, x_i​ (1 \leq y_i \leq N, 1 \leq x_i \leq M)를 포함한다.


輸出

유효 상태의 총 개수를 10^9 + 7로 나눈 나머지를 출력한다.


子任務

編號 分數 條件
#112分

N, M ≤ 5

#242分

N, M ≤ 1 000

#346分

추가 제약 조건 없음


範例 #1

2 4 4
+ 1 1
- 1 2
+ 1 3
- 1 4
2

가능한 전자 격자는 아래와 같은 두 형태이다.

+-+-
+-+-
+-+-
-+-+

範例 #2

3 3 3
- 2 1
+ 2 3
+ 3 3
0


來源

BOI 2017 F번

需要登入才能撰寫程式碼。