結果

問題 No.895 MESE
ユーザー e869120e869120
提出日時 2019-09-15 14:06:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 372 ms / 2,000 ms
コード長 2,098 bytes
コンパイル時間 556 ms
コンパイル使用メモリ 66,416 KB
実行使用メモリ 12,908 KB
最終ジャッジ日時 2024-07-06 22:44:10
合計ジャッジ時間 12,376 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 358 ms
12,664 KB
testcase_01 AC 357 ms
12,672 KB
testcase_02 AC 357 ms
12,672 KB
testcase_03 AC 360 ms
12,800 KB
testcase_04 AC 358 ms
12,800 KB
testcase_05 AC 356 ms
12,672 KB
testcase_06 AC 357 ms
12,800 KB
testcase_07 AC 357 ms
12,800 KB
testcase_08 AC 356 ms
12,824 KB
testcase_09 AC 357 ms
12,800 KB
testcase_10 AC 357 ms
12,800 KB
testcase_11 AC 358 ms
12,800 KB
testcase_12 AC 356 ms
12,800 KB
testcase_13 AC 362 ms
12,908 KB
testcase_14 AC 368 ms
12,800 KB
testcase_15 AC 369 ms
12,800 KB
testcase_16 AC 365 ms
12,672 KB
testcase_17 AC 359 ms
12,672 KB
testcase_18 AC 370 ms
12,856 KB
testcase_19 AC 369 ms
12,800 KB
testcase_20 AC 372 ms
12,800 KB
testcase_21 AC 370 ms
12,800 KB
testcase_22 AC 371 ms
12,800 KB
testcase_23 AC 370 ms
12,800 KB
testcase_24 AC 370 ms
12,800 KB
testcase_25 AC 372 ms
12,720 KB
testcase_26 AC 371 ms
12,800 KB
testcase_27 AC 371 ms
12,800 KB
testcase_28 AC 369 ms
12,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cassert>
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)) != 0) { 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 fact[300009], factinv[300009], inv[300009], power2[300009];
long long A, B, C;

void init() {
	fact[0] = 1;
	for (int i = 1; i <= 300000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 300000; i++) factinv[i] = Div(1, fact[i], mod);
	for (int i = 1; i <= 300000; i++) inv[i] = Div(1, i, mod);

	power2[0] = 1;
	for (int i = 1; i <= 300000; i++) power2[i] = (2LL * power2[i - 1]) % mod;
}

long long ncr(long long n, long long r) {
	if (n < r || r < 0) return 0LL;
	return (fact[n] * factinv[r] % mod) * factinv[n - r] % mod;
}

int main() {
	init();
	cin >> A >> B >> C;
	assert(1 <= A && A <= 100000);
	assert(1 <= B && B <= 100000);
	assert(1 <= C && C <= 100000);

	// Y の合計を求める
	long long Y = 0, TotalWays = 0;
	for (int i = 1; i <= A; i++) {
		long long Y1 = power2[A + B + C - i - 1] - 1LL;
		long long Y2 = (B - 1LL) * inv[A + B + C - i - 1] % mod;
		long long Y3 = ncr(B + C - 1, B - 1) * ncr(A + B + C - i - 1, A - i) % mod;
		long long YY = (Y1 * Y2 % mod) * Y3 % mod;
		Y += YY; Y %= mod;
		Y += power2[A + B + C - i - 1] * Y3 % mod; Y %= mod;
		TotalWays += Y3; TotalWays %= mod;
	}

	// X の合計を求める
	long long X1 = power2[A + B + C - 1] - 1LL;
	long long X2 = (A - 1LL) * inv[A + B + C - 1] % mod;
	long long X3 = TotalWays;
	long long X = 0;
	X += (X1 * X2 % mod) * X3 % mod;
	X += power2[A + B + C - 1] * X3 % mod;
	X %= mod;

	// X + Y + Z の合計を求める
	long long Total = 0;
	long long T1 = TotalWays;
	long long T2 = power2[A + B + C] - 1LL;
	Total = T1 * T2 % mod;

	// 最後に出力する
	long long Answer = (Total - X - Y + mod * 2LL) % mod;
	cout << Answer << endl;
	assert(0 <= Answer && Answer <= 1000000006);
	return 0;
}
0