結果

問題 No.1596 Distance Sum in 2D Plane
ユーザー e869120e869120
提出日時 2021-05-03 15:06:26
言語 C++14
(gcc 12.2.0 + boost 1.81.0)
結果
AC  
実行時間 983 ms / 2,000 ms
コード長 1,518 bytes
コンパイル時間 503 ms
コンパイル使用メモリ 64,852 KB
実行使用メモリ 26,200 KB
最終ジャッジ日時 2023-09-14 06:42:14
合計ジャッジ時間 22,035 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 802 ms
19,784 KB
testcase_01 AC 803 ms
25,936 KB
testcase_02 AC 980 ms
25,860 KB
testcase_03 AC 980 ms
25,936 KB
testcase_04 AC 982 ms
25,872 KB
testcase_05 AC 982 ms
26,200 KB
testcase_06 AC 982 ms
25,924 KB
testcase_07 AC 983 ms
25,884 KB
testcase_08 AC 975 ms
25,860 KB
testcase_09 AC 980 ms
25,912 KB
testcase_10 AC 979 ms
25,864 KB
testcase_11 AC 952 ms
25,884 KB
testcase_12 AC 952 ms
25,864 KB
testcase_13 AC 951 ms
25,880 KB
testcase_14 AC 805 ms
19,780 KB
testcase_15 AC 805 ms
25,916 KB
testcase_16 AC 806 ms
25,992 KB
testcase_17 AC 806 ms
25,924 KB
testcase_18 AC 801 ms
19,736 KB
testcase_19 AC 804 ms
25,924 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b / (1LL << i)) % 2LL == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

long long mod = 1000000007;
long long N, M;
long long A[1 << 18], B[1 << 18], C[1 << 18];
long long fact[1 << 20], factinv[1 << 20];

long long ncr(long long n, long long r) {
	return (fact[n] * factinv[r] % mod) * factinv[n - r] % mod;
}

long long keiro(long long a, long long b) {
	// (0, 0) から (a, b) まで移動する方法の総数
	return ncr(a + b, b);
}

int main() {
	// Step #1. Input
	cin >> N >> M;
	for (int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i];

	// Step #2. Prepare
	fact[0] = 1;
	for (int i = 1; i <= 1000000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 1000000; i++) factinv[i] = Div(1, fact[i], mod);

	// Step #3. Solve
	long long Answer = (2LL * N) * keiro(N, N) % mod;
	for (int i = 1; i <= M; i++) {
		if (A[i] == 1) {
			long long p1 = keiro(B[i], C[i]);
			long long p2 = keiro(N - (B[i] + 1LL), N - C[i]);
			Answer -= p1 * p2 % mod;
			Answer = (Answer + mod) % mod;
		}
		if (A[i] == 2) {
			long long p1 = keiro(B[i], C[i]);
			long long p2 = keiro(N - B[i], N - (C[i] + 1LL));
			Answer -= p1 * p2 % mod;
			Answer = (Answer + mod) % mod;
		}
	}

	// Step #4. Output
	cout << Answer << endl;
	return 0;
}
0