結果
問題 |
No.1683 Robot Guidance
|
ユーザー |
![]() |
提出日時 | 2021-09-17 22:42:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 297 ms / 2,000 ms |
コード長 | 2,489 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 238,860 KB |
最終ジャッジ日時 | 2024-06-29 21:27:31 |
合計ジャッジ時間 | 12,588 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
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)