結果
問題 | No.1683 Robot Guidance |
ユーザー | neterukun |
提出日時 | 2021-09-17 22:42:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 359 ms / 2,000 ms |
コード長 | 2,489 bytes |
コンパイル時間 | 280 ms |
コンパイル使用メモリ | 86,600 KB |
実行使用メモリ | 252,772 KB |
最終ジャッジ日時 | 2023-09-12 08:43:00 |
合計ジャッジ時間 | 15,534 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 305 ms
252,264 KB |
testcase_01 | AC | 308 ms
252,256 KB |
testcase_02 | AC | 307 ms
252,336 KB |
testcase_03 | AC | 318 ms
252,168 KB |
testcase_04 | AC | 318 ms
252,268 KB |
testcase_05 | AC | 318 ms
252,772 KB |
testcase_06 | AC | 322 ms
252,108 KB |
testcase_07 | AC | 322 ms
252,132 KB |
testcase_08 | AC | 359 ms
252,124 KB |
testcase_09 | AC | 323 ms
252,572 KB |
testcase_10 | AC | 340 ms
252,340 KB |
testcase_11 | AC | 329 ms
252,184 KB |
testcase_12 | AC | 357 ms
252,444 KB |
testcase_13 | AC | 315 ms
252,064 KB |
testcase_14 | AC | 343 ms
252,328 KB |
testcase_15 | AC | 332 ms
252,548 KB |
testcase_16 | AC | 321 ms
252,544 KB |
testcase_17 | AC | 316 ms
252,124 KB |
testcase_18 | AC | 310 ms
252,244 KB |
testcase_19 | AC | 308 ms
252,740 KB |
testcase_20 | AC | 310 ms
252,352 KB |
testcase_21 | AC | 315 ms
252,376 KB |
testcase_22 | AC | 308 ms
252,488 KB |
testcase_23 | AC | 316 ms
252,332 KB |
testcase_24 | AC | 359 ms
252,184 KB |
testcase_25 | AC | 319 ms
252,212 KB |
testcase_26 | AC | 321 ms
252,248 KB |
testcase_27 | AC | 329 ms
252,536 KB |
testcase_28 | AC | 313 ms
252,144 KB |
testcase_29 | AC | 316 ms
252,316 KB |
testcase_30 | AC | 317 ms
252,232 KB |
testcase_31 | AC | 318 ms
252,324 KB |
testcase_32 | AC | 320 ms
252,252 KB |
testcase_33 | AC | 335 ms
252,680 KB |
testcase_34 | AC | 336 ms
252,216 KB |
testcase_35 | AC | 328 ms
252,248 KB |
testcase_36 | AC | 328 ms
252,176 KB |
testcase_37 | AC | 333 ms
252,540 KB |
testcase_38 | AC | 332 ms
252,316 KB |
testcase_39 | AC | 326 ms
252,252 KB |
testcase_40 | AC | 304 ms
252,448 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 yp_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)