結果
問題 | No.1141 田グリッド |
ユーザー |
|
提出日時 | 2020-07-31 21:52:29 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 675 ms / 2,000 ms |
コード長 | 1,740 bytes |
コンパイル時間 | 256 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 32,296 KB |
最終ジャッジ日時 | 2024-07-06 17:46:30 |
合計ジャッジ時間 | 15,223 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#!/usr/bin/env python3from typing import *MOD = 1000000007def solve(h: int, w: int, a: List[List[int]], q: int, r: List[int], c: List[int]) -> List[int]:all_prod = 1all_zero = 0row_prod = [1] * hcol_prod = [1] * wrow_zero = [0] * hcol_zero = [0] * wfor y in range(h):for x in range(w):if a[y][x] == 0:row_zero[y] += 1col_zero[x] += 1else:row_prod[y] = row_prod[y] * a[y][x] % MODcol_prod[x] = col_prod[x] * a[y][x] % MODall_prod = all_prod * row_prod[y] % MODall_zero += row_zero[y]ans = []for y, x in zip(r, c):prod = all_prod * pow(row_prod[y], MOD - 2, MOD) * pow(col_prod[x], MOD - 2, MOD)zero = all_zero - row_zero[y] - col_zero[x]if a[y][x] == 0:zero += 1else:prod *= a[y][x]prod %= MODif zero:ans.append(0)else:ans.append(prod)return ans# generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator)def main():import systokens = iter(sys.stdin.read().split())H = int(next(tokens))W = int(next(tokens))A = [[None for _ in range(W)] for _ in range(H)]for j in range(H):for i in range(W):A[j][i] = int(next(tokens))Q = int(next(tokens))r = [None for _ in range(Q)]c = [None for _ in range(Q)]for i in range(Q):r[i] = int(next(tokens)) - 1c[i] = int(next(tokens)) - 1assert next(tokens, None) is Noneans = solve(H, W, A, Q, r, c)print(*ans, sep='\n')if __name__ == '__main__':main()