結果
問題 |
No.1141 田グリッド
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:48:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 958 ms / 2,000 ms |
コード長 | 2,632 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 108,576 KB |
最終ジャッジ日時 | 2025-03-20 20:48:18 |
合計ジャッジ時間 | 8,842 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read().split() idx = 0 H = int(input[idx]); idx +=1 W = int(input[idx]); idx +=1 grid = [] for _ in range(H): row = list(map(int, input[idx:idx+W])) idx += W grid.append(row) row_product = [1] * H row_zero = [0] * H col_product = [1] * W col_zero = [0] * W total_product = 1 total_zero = 0 for i in range(H): p = 1 cnt = 0 for val in grid[i]: p = p * val % MOD if val == 0: cnt += 1 row_product[i] = p row_zero[i] = cnt for j in range(W): p = 1 cnt = 0 for i in range(H): val = grid[i][j] p = p * val % MOD if val == 0: cnt += 1 col_product[j] = p col_zero[j] = cnt total_zero = 0 for i in range(H): total_zero += row_zero[i] has_zero = any(val == 0 for row in grid for val in row) total_product = 1 for i in range(H): for j in range(W): total_product = total_product * grid[i][j] % MOD Q = int(input[idx]); idx +=1 for _ in range(Q): r, c = int(input[idx])-1, int(input[idx+1])-1 # convert to 0-based idx +=2 # Calculate the remaining zeros rem_zero = total_zero - row_zero[r] - col_zero[c] + (1 if grid[r][c] == 0 else 0) if rem_zero > 0: print(0) continue if total_product != 0: # Use formula rp = row_product[r] cp = col_product[c] cross = grid[r][c] numerator = total_product denominator = (rp * cp) % MOD denom_inv = pow(denominator, MOD-2, MOD) res = numerator * denom_inv % MOD res = res * cross % MOD print(res) else: # Need to compute product directly prod = 1 zero_found = False for i in range(H): if i == r: continue for j in range(W): if j == c: continue val = grid[i][j] if val == 0: zero_found = True break prod = prod * val % MOD if zero_found: break if zero_found: print(0) else: print(prod % MOD) if __name__ == '__main__': main()