結果
問題 | No.1141 田グリッド |
ユーザー | persimmon-persimmon |
提出日時 | 2021-06-17 11:31:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 434 ms / 2,000 ms |
コード長 | 2,118 bytes |
コンパイル時間 | 1,155 ms |
コンパイル使用メモリ | 86,836 KB |
実行使用メモリ | 107,608 KB |
最終ジャッジ日時 | 2023-08-30 19:31:29 |
合計ジャッジ時間 | 9,440 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 86 ms
72,188 KB |
testcase_01 | AC | 86 ms
72,444 KB |
testcase_02 | AC | 88 ms
72,056 KB |
testcase_03 | AC | 90 ms
71,964 KB |
testcase_04 | AC | 86 ms
72,076 KB |
testcase_05 | AC | 87 ms
72,184 KB |
testcase_06 | AC | 87 ms
71,892 KB |
testcase_07 | AC | 85 ms
72,136 KB |
testcase_08 | AC | 113 ms
78,672 KB |
testcase_09 | AC | 107 ms
78,204 KB |
testcase_10 | AC | 113 ms
78,484 KB |
testcase_11 | AC | 108 ms
78,204 KB |
testcase_12 | AC | 119 ms
78,732 KB |
testcase_13 | AC | 356 ms
98,204 KB |
testcase_14 | AC | 434 ms
107,608 KB |
testcase_15 | AC | 363 ms
89,368 KB |
testcase_16 | AC | 371 ms
89,244 KB |
testcase_17 | AC | 371 ms
89,900 KB |
testcase_18 | AC | 207 ms
91,900 KB |
testcase_19 | AC | 209 ms
91,800 KB |
testcase_20 | AC | 210 ms
91,856 KB |
testcase_21 | AC | 365 ms
89,016 KB |
testcase_22 | AC | 365 ms
89,032 KB |
testcase_23 | AC | 360 ms
89,048 KB |
testcase_24 | AC | 205 ms
90,988 KB |
testcase_25 | AC | 200 ms
90,312 KB |
testcase_26 | AC | 212 ms
91,080 KB |
testcase_27 | AC | 212 ms
91,308 KB |
testcase_28 | AC | 206 ms
90,612 KB |
testcase_29 | AC | 206 ms
91,136 KB |
testcase_30 | AC | 217 ms
91,428 KB |
testcase_31 | AC | 201 ms
90,632 KB |
testcase_32 | AC | 200 ms
90,528 KB |
testcase_33 | AC | 198 ms
90,772 KB |
ソースコード
def main0(h,w,a,q,rc): mod=10**9+7 ans=[] for r,c in rc: r,c=r-1,c-1 tmp=1 for i in range(h): if i==r:continue for j in range(w): if j==c:continue tmp*=a[i][j] tmp%=mod ans.append(tmp) return ans def main1(h,w,a,q,rc): mod=10**9+7 mat=[] mat.append([1]*(w+1)) ary0=[] ary0.append([0]*(w+1)) for i in range(h): tmp=[1] tmp0=[0] for j in range(w): if a[i][j]: tmp.append(tmp[-1]*a[i][j]%mod) tmp0.append(tmp0[-1]) else: tmp.append(tmp[-1]) tmp0.append(tmp0[-1]+1) mat.append(tmp) ary0.append(tmp0) for j in range(w+1): for i in range(h): mat[i+1][j]*=mat[i][j] mat[i+1][j]%=mod ary0[i+1][j]+=ary0[i][j] ans=[] #for x in mat:print(x) for r,c in rc: r,c=r-1,c-1 # 0含むかどうかチェック t=ary0[r][c] t+=ary0[-1][c]-ary0[r+1][c] t+=ary0[r][-1]-ary0[r][c+1] t+=ary0[-1][-1]+ary0[r+1][c+1]-ary0[r+1][-1]-ary0[-1][c+1] if t: ans.append(0) continue tmp0=mat[r][c] # 左上 tmp1=mat[-1][c]*pow(mat[r+1][c],mod-2,mod)%mod # 左下 tmp2=mat[r][-1]*pow(mat[r][c+1],mod-2,mod)%mod # 右上 tmp3=mat[-1][-1]*mat[r+1][c+1]%mod # 右下 tmp3=tmp3*pow(mat[r+1][-1],mod-2,mod)*pow(mat[-1][c+1],mod-2,mod)%mod # 右下 ans.append(tmp0*tmp1*tmp2*tmp3%mod) return ans if __name__=='__main__': h,w=map(int,input().split()) a=[list(map(int,input().split())) for _ in range(h)] q=int(input()) rc=[list(map(int,input().split())) for _ in range(q)] #ret0=main0(h,w,a,q,rc) #print(ret0) ret1=main1(h,w,a,q,rc) print(*ret1,sep="\n") from random import randint if __name__=='__main__1': for _ in range(100): h=randint(2,6) w=randint(2,6) a=[[randint(0,6) for _ in range(w)] for _ in range(h)] q=randint(2,6) rc=[[randint(1,h),randint(1,w)]for _ in range(q)] ret0=main0(h,w,a,q,rc) ret1=main1(h,w,a,q,rc) if ret0!=ret1: print(h,w) for x in a:print(*x) print(q) for x in rc:print(*x) print(ret0) print(ret1) break