結果
問題 | No.1141 田グリッド |
ユーザー | tktk_snsn |
提出日時 | 2020-12-23 22:26:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 223 ms / 2,000 ms |
コード長 | 1,383 bytes |
コンパイル時間 | 866 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 102,316 KB |
最終ジャッジ日時 | 2023-10-21 15:20:31 |
合計ジャッジ時間 | 5,971 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
55,504 KB |
testcase_01 | AC | 42 ms
55,504 KB |
testcase_02 | AC | 42 ms
55,504 KB |
testcase_03 | AC | 42 ms
55,504 KB |
testcase_04 | AC | 42 ms
55,504 KB |
testcase_05 | AC | 43 ms
55,504 KB |
testcase_06 | AC | 42 ms
55,504 KB |
testcase_07 | AC | 42 ms
55,504 KB |
testcase_08 | AC | 60 ms
66,388 KB |
testcase_09 | AC | 56 ms
66,376 KB |
testcase_10 | AC | 59 ms
66,388 KB |
testcase_11 | AC | 57 ms
66,512 KB |
testcase_12 | AC | 65 ms
70,528 KB |
testcase_13 | AC | 176 ms
97,932 KB |
testcase_14 | AC | 223 ms
102,316 KB |
testcase_15 | AC | 138 ms
93,608 KB |
testcase_16 | AC | 135 ms
93,608 KB |
testcase_17 | AC | 138 ms
93,608 KB |
testcase_18 | AC | 94 ms
77,092 KB |
testcase_19 | AC | 96 ms
77,016 KB |
testcase_20 | AC | 93 ms
77,024 KB |
testcase_21 | AC | 134 ms
93,608 KB |
testcase_22 | AC | 138 ms
93,608 KB |
testcase_23 | AC | 135 ms
93,608 KB |
testcase_24 | AC | 104 ms
77,216 KB |
testcase_25 | AC | 113 ms
78,300 KB |
testcase_26 | AC | 106 ms
77,304 KB |
testcase_27 | AC | 112 ms
77,312 KB |
testcase_28 | AC | 113 ms
77,940 KB |
testcase_29 | AC | 98 ms
77,144 KB |
testcase_30 | AC | 101 ms
77,248 KB |
testcase_31 | AC | 107 ms
77,288 KB |
testcase_32 | AC | 96 ms
77,164 KB |
testcase_33 | AC | 96 ms
77,164 KB |
ソースコード
from collections import defaultdict import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) mod = 10 ** 9 + 7 H, W = map(int, input().split()) A = list(list(map(int, input().split())) for _ in range(H)) zero = 0 cnt_row = [0] * H cnt_col = [0] * W ALL = 1 row = [1] * H col = [1] * W for i, ai in enumerate(A): for j, a in enumerate(ai): if a == 0: zero += 1 cnt_row[i] += 1 cnt_col[j] += 1 else: ALL = ALL * a % mod row[i] = row[i] * a % mod col[j] = col[j] * a % mod for i in range(H): row[i] = pow(row[i], mod-2, mod) for j in range(W): col[j] = pow(col[j], mod-2, mod) safe = set() dr = defaultdict(list) dc = defaultdict(list) for i, c in enumerate(cnt_row): dr[c].append(i) for i, c in enumerate(cnt_col): dc[c].append(i) for k, v in dr.items(): for c in dc[zero - k]: for r in v: if A[r][c] != 0: safe.add((r, c)) for c in dc[zero - k + 1]: for r in v: if A[r][c] == 0: safe.add((r, c)) Q = int(input()) for _ in range(Q): r, c = map(int, input().split()) r -= 1 c -= 1 if zero == 0 or (r, c) in safe: res = ALL * row[r] * col[c] % mod if A[r][c] != 0: res *= A[r][c] print(res % mod) else: print(0)