結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー | ks2m |
提出日時 | 2021-07-09 21:50:46 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 505 ms / 2,000 ms |
コード長 | 1,699 bytes |
コンパイル時間 | 2,143 ms |
コンパイル使用メモリ | 74,780 KB |
実行使用メモリ | 62,244 KB |
最終ジャッジ日時 | 2023-09-14 08:33:50 |
合計ジャッジ時間 | 10,007 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
55,444 KB |
testcase_01 | AC | 74 ms
55,284 KB |
testcase_02 | AC | 487 ms
61,620 KB |
testcase_03 | AC | 481 ms
62,144 KB |
testcase_04 | AC | 490 ms
61,852 KB |
testcase_05 | AC | 479 ms
62,244 KB |
testcase_06 | AC | 487 ms
61,628 KB |
testcase_07 | AC | 502 ms
61,916 KB |
testcase_08 | AC | 505 ms
61,636 KB |
testcase_09 | AC | 501 ms
61,900 KB |
testcase_10 | AC | 487 ms
61,708 KB |
testcase_11 | AC | 470 ms
61,484 KB |
testcase_12 | AC | 459 ms
61,672 KB |
testcase_13 | AC | 474 ms
61,700 KB |
testcase_14 | AC | 47 ms
49,712 KB |
testcase_15 | AC | 45 ms
49,628 KB |
testcase_16 | AC | 46 ms
49,732 KB |
testcase_17 | AC | 45 ms
49,788 KB |
testcase_18 | AC | 45 ms
49,740 KB |
testcase_19 | AC | 45 ms
49,972 KB |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int m = Integer.parseInt(sa[1]); int[] t = new int[m]; int[] x = new int[m]; int[] y = new int[m]; for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); t[i] = Integer.parseInt(sa[0]); x[i] = Integer.parseInt(sa[1]); y[i] = Integer.parseInt(sa[2]); } br.close(); int mod = 1000000007; Kaijou kai = new Kaijou(n * 2, mod); long ans = kai.comb(n * 2, n) * n * 2 % mod; for (int i = 0; i < m; i++) { long v1 = kai.comb(x[i] + y[i], x[i]); long v2 = 0; if (t[i] == 1) { v2 = kai.comb(n * 2 - x[i] - y[i] - 1, n - x[i] - 1); } else { v2 = kai.comb(n * 2 - x[i] - y[i] - 1, n - x[i]); } long val = v1 * v2 % mod; ans = ans - val + mod; ans %= mod; } System.out.println(ans); } static class Kaijou { long[] p, pi; int m; public Kaijou(int n, int mod) { n++; m = mod; p = new long[n]; pi = new long[n]; p[0] = 1; pi[0] = 1; for (int i = 1; i < n; i++) { p[i] = p[i - 1] * i % m; } pi[n - 1] = BigInteger.valueOf(p[n - 1]) .modInverse(BigInteger.valueOf(m)).longValue(); for (int i = n - 1; i > 1; i--) { pi[i - 1] = pi[i] * i % m; } } public long comb(int n, int r) { if (n < r) return 0; return p[n] * pi[r] % m * pi[n - r] % m; } public long perm(int n, int r) { if (n < r) return 0; return p[n] * pi[n - r] % m; } } }