結果
問題 | No.1520 Zigzag Sum |
ユーザー |
👑 ![]() |
提出日時 | 2021-05-28 20:53:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 186 ms / 2,000 ms |
コード長 | 969 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 117,504 KB |
最終ジャッジ日時 | 2024-11-07 08:27:01 |
合計ジャッジ時間 | 2,276 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 |
ソースコード
"""→,↓を並べる全ての場所に関して、異なる場合の数を求めればよいH+W-1 * ()"""from sys import stdinimport sysdef modfac(n, MOD):f = 1factorials = [1]for m in range(1, n + 1):f *= mf %= MODfactorials.append(f)inv = pow(f, MOD - 2, MOD)invs = [1] * (n + 1)invs[n] = invfor m in range(n, 1, -1):inv *= minv %= MODinvs[m - 1] = invreturn factorials, invsdef modnCr(n,r): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)return fac[n] * inv[n-r] * inv[r] % modmod = 10**9+7fac,inv = modfac(500000,mod)TT = int(stdin.readline())ANS = []for loop in range(TT):H,W = map(int,stdin.readline().split())if min(H,W) == 1:ans = 0else:ans = (H+W-3) * 2 * modnCr(H+W-4,H-2)ANS.append(str(ans % mod))print ("\n".join(ANS))