結果
問題 | No.1683 Robot Guidance |
ユーザー | neterukun |
提出日時 | 2021-09-17 22:41:48 |
言語 | PyPy3 (7.3.13) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,489 bytes |
コンパイル時間 | 833 ms |
コンパイル使用メモリ | 86,832 KB |
実行使用メモリ | 253,064 KB |
最終ジャッジ日時 | 2023-09-12 08:42:07 |
合計ジャッジ時間 | 15,131 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 300 ms
252,268 KB |
testcase_01 | AC | 299 ms
252,360 KB |
testcase_02 | AC | 302 ms
252,456 KB |
testcase_03 | WA | - |
testcase_04 | AC | 313 ms
252,648 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 353 ms
252,724 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 322 ms
252,680 KB |
testcase_12 | AC | 351 ms
252,296 KB |
testcase_13 | AC | 310 ms
252,376 KB |
testcase_14 | WA | - |
testcase_15 | AC | 321 ms
252,464 KB |
testcase_16 | AC | 309 ms
252,440 KB |
testcase_17 | AC | 308 ms
252,660 KB |
testcase_18 | AC | 305 ms
253,004 KB |
testcase_19 | AC | 301 ms
252,936 KB |
testcase_20 | AC | 298 ms
252,532 KB |
testcase_21 | AC | 305 ms
252,464 KB |
testcase_22 | AC | 299 ms
252,456 KB |
testcase_23 | AC | 307 ms
252,676 KB |
testcase_24 | WA | - |
testcase_25 | AC | 306 ms
252,396 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 306 ms
252,372 KB |
testcase_29 | AC | 307 ms
252,400 KB |
testcase_30 | AC | 308 ms
252,200 KB |
testcase_31 | AC | 310 ms
252,344 KB |
testcase_32 | AC | 312 ms
252,296 KB |
testcase_33 | AC | 327 ms
252,256 KB |
testcase_34 | AC | 326 ms
252,396 KB |
testcase_35 | AC | 322 ms
252,456 KB |
testcase_36 | AC | 321 ms
252,212 KB |
testcase_37 | AC | 339 ms
252,500 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | AC | 299 ms
252,424 KB |
ソースコード
class Combination: def __init__(self, n, MOD): self.f = [1] for i in range(1, n + 1): self.f.append(self.f[-1] * i % MOD) self.inv_f = [0] * (n + 1) self.inv_f[n] = pow(self.f[n], MOD - 2, MOD) for i in reversed(range(n)): self.inv_f[i] = self.inv_f[i + 1] * (i + 1) % MOD self.MOD = MOD def inv(self, k): """get inverse(k)""" return (self.inv_f[k] * self.f[k - 1]) % self.MOD def fact(self, k): """get k!""" return self.f[k] def inv_fact(self, k): """get inverse(k!)""" return self.inv_f[k] def perm(self, k, r): """get kPr""" if k < r: return 0 return (self.f[k] * self.inv_f[k - r]) % self.MOD def comb(self, k, r): """get kCr""" if k < r: return 0 return (self.f[k] * self.inv_f[k - r] % self.MOD * self.inv_f[r]) % self.MOD def way4(ball, box): """ball: False / box: True / constraints: None -> ans = comb(box + ball - 1, ball) """ if box == 0 and ball == 0: return 1 if box == 0: return 0 if ball == 0: return 1 return comb.comb(ball + box - 1, ball) # 区別するbox個の箱 -> 区別しない(box - 1)個の仕切に変換して解く a, b, x, y = map(int, input().split()) MOD = 10 ** 9 + 7 comb = Combination(3 * 10 ** 6, MOD) def answer(a, b, x, y): def solve(xp_cnt, xm_cnt, yp_cnt, ym_cnt): res = 1 res = res * way4(xp_cnt, xp) % MOD res = res * way4(xm_cnt, xm) % MOD res = res * way4(yp_cnt, yp) % MOD res = res * way4(ym_cnt, ym) % MOD return res bucket = [1, 0, 0, 0] for i in range(b): i += 1 bucket[i % 4] += 1 xp, yp, xm, ym = bucket ans = 0 for i in range(a + 1): cntx = i cnty = a - i xp_cnt = (cntx + x) xm_cnt = (cntx - x) yp_cnt = (cnty + y) ym_cnt = (cnty - y) if xp_cnt % 2 == 1 or xp_cnt < 0: continue if xm_cnt % 2 == 1 or xm_cnt < 0: continue if yp_cnt % 2 == 1 or xp_cnt < 0: continue if ym_cnt % 2 == 1 or ym_cnt < 0: continue xp_cnt //= 2 xm_cnt //= 2 yp_cnt //= 2 ym_cnt //= 2 ans += solve(xp_cnt, xm_cnt, yp_cnt, ym_cnt) ans %= MOD return ans print(answer(a, b, x, y) % MOD)