結果
問題 | No.1683 Robot Guidance |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-09-17 22:16:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 585 ms / 2,000 ms |
コード長 | 1,610 bytes |
コンパイル時間 | 1,447 ms |
コンパイル使用メモリ | 87,000 KB |
実行使用メモリ | 248,104 KB |
最終ジャッジ日時 | 2023-09-12 07:58:26 |
合計ジャッジ時間 | 15,488 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 326 ms
246,572 KB |
testcase_01 | AC | 291 ms
246,364 KB |
testcase_02 | AC | 311 ms
247,180 KB |
testcase_03 | AC | 322 ms
247,512 KB |
testcase_04 | AC | 320 ms
247,280 KB |
testcase_05 | AC | 309 ms
248,104 KB |
testcase_06 | AC | 339 ms
247,392 KB |
testcase_07 | AC | 307 ms
247,404 KB |
testcase_08 | AC | 543 ms
247,892 KB |
testcase_09 | AC | 318 ms
247,924 KB |
testcase_10 | AC | 429 ms
247,728 KB |
testcase_11 | AC | 439 ms
247,756 KB |
testcase_12 | AC | 556 ms
247,816 KB |
testcase_13 | AC | 275 ms
246,552 KB |
testcase_14 | AC | 483 ms
247,512 KB |
testcase_15 | AC | 317 ms
247,888 KB |
testcase_16 | AC | 271 ms
246,584 KB |
testcase_17 | AC | 271 ms
246,596 KB |
testcase_18 | AC | 275 ms
246,892 KB |
testcase_19 | AC | 276 ms
246,544 KB |
testcase_20 | AC | 279 ms
246,640 KB |
testcase_21 | AC | 299 ms
247,244 KB |
testcase_22 | AC | 272 ms
246,552 KB |
testcase_23 | AC | 263 ms
246,896 KB |
testcase_24 | AC | 585 ms
247,704 KB |
testcase_25 | AC | 279 ms
246,536 KB |
testcase_26 | AC | 274 ms
246,596 KB |
testcase_27 | AC | 262 ms
246,600 KB |
testcase_28 | AC | 276 ms
246,676 KB |
testcase_29 | AC | 260 ms
246,676 KB |
testcase_30 | AC | 260 ms
246,680 KB |
testcase_31 | AC | 273 ms
246,724 KB |
testcase_32 | AC | 258 ms
246,584 KB |
testcase_33 | AC | 296 ms
247,572 KB |
testcase_34 | AC | 294 ms
247,580 KB |
testcase_35 | AC | 286 ms
247,348 KB |
testcase_36 | AC | 291 ms
247,204 KB |
testcase_37 | AC | 269 ms
247,208 KB |
testcase_38 | AC | 276 ms
247,256 KB |
testcase_39 | AC | 269 ms
246,596 KB |
testcase_40 | AC | 268 ms
246,752 KB |
ソースコード
""" 1,2,4,8,16,32,64,128 x+ y+ x- y- Gを割り振ることを考える x,y にとりあえず割り当ててしまう 残りは、x,yの割り当てかたが 10^6個ぐらいある。 また、それぞれに何回訪れられるかがわかる 適当に計算すれば終わり これで、O(G) """ import sys from sys import stdin def modfac(n, MOD): f = 1 factorials = [1] for m in range(1, n + 1): f *= m f %= MOD factorials.append(f) inv = pow(f, MOD - 2, MOD) invs = [1] * (n + 1) invs[n] = inv for m in range(n, 1, -1): inv *= m inv %= MOD invs[m - 1] = inv return factorials, invs def modnCr(n,r): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる) return fac[n] * inv[n-r] * inv[r] % mod mod = 10**9+7 fac,inv = modfac(2*(10**6),mod) G,T,X,Y = map(int,stdin.readline().split()) T += 1 A,B,C,D = 0,0,0,0 if X > 0: A = X else: C = -X if Y > 0: B = Y else: D = -Y rem = G - abs(X) - abs(Y) if rem < 0 or rem % 2 == 1: print (0) sys.exit() ans = 0 for xput in range(rem//2+1): yput = rem//2 - xput Glis = [A+xput,B+yput,C+xput,D+yput] of = T // 4 Tlis = [of] * 4 orem = T % 4 for i in range(orem): Tlis[i] += 1 nans = 1 for i in range(4): if Glis[i] > 0 and Tlis[i] == 0: nans = 0 break else: nans *= modnCr(Glis[i]+Tlis[i]-1,Tlis[i]-1) ans += nans #print (Glis,Tlis,nans) ans %= mod print (ans)