結果

問題 No.584 赤、緑、青の色塗り
ユーザー ats5515ats5515
提出日時 2017-10-28 00:21:15
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,931 bytes
コンパイル時間 709 ms
コンパイル使用メモリ 83,300 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-11-22 00:03:28
合計ジャッジ時間 4,577 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 3 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 3 ms
5,248 KB
testcase_14 AC 21 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 6 ms
5,248 KB
testcase_17 AC 90 ms
5,248 KB
testcase_18 AC 15 ms
5,248 KB
testcase_19 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
template <typename Int, Int MOD, int N>
struct comb_util {
	std::array<Int, N + 1> fc, ifc;

	comb_util() {
		fc[0] = 1;
		for (int i = 1; i <= N; i++) fc[i] = fc[i - 1] * i % MOD;
		ifc[N] = inv(fc[N]);
		for (int i = N - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % MOD;
	}

	Int fact(Int n) { return fc[n]; }

	Int inv_fact(Int n) { return ifc[n]; }

	Int inv(Int n) { return pow(n, MOD - 2); }

	Int pow(Int n, Int a) {
		Int res = 1, exp = n;
		for (; a; a /= 2) {
			if (a & 1) res = res * exp % MOD;
			exp = exp * exp % MOD;
		}
		return res;
	}

	Int perm(Int n, Int r) {
		if (r < 0 || n < r)
			return 0;
		else
			return fc[n] * ifc[n - r] % MOD;
	}

	Int binom(Int n, Int r) {
		if (n < 0 || r < 0 || n < r) return 0;
		return fc[n] * ifc[r] % MOD * ifc[n - r] % MOD;
	}

	Int homo(Int n, Int r) {
		if (n < 0 || r < 0) return 0;
		return r == 0 ? 1 : binom(n + r - 1, r);
	}
};

using comb = comb_util<long long, 1000000007, 30000>;
comb cb;
int myhash(int a, int b, int c) {
	if (a > b) {
		swap(a, b);
	}
	if (b > c) {
		swap(c, b);
	}
	if (a > b) {
		swap(a, b);
	}
	return a * 1000000 + b * 1000 + c;
}
void unhash(int &a,int &b,int &c,int h) {
	c = h % 1000;
	h /= 1000;
	b = h % 1000;
	h /= 1000;
	a = h;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, A, B, C;
	cin >> N >> A >> B >> C;
	int res = 0;
	int t;
	int x1, x2, x3;
	int tt;
	if (A + B + C > (2.0*3.0) * (N + 1)) {
		cout << 0 << endl;
		return 0;
	}
	for (int x = 0; x <= A + B + C; x++) {
		int y = (A + B + C - x) / 2;
		if (x + 2 * y == A + B + C) {
			if (x + 2 * y + x + y <= N + 1) {
				t = 0;
				t = cb.homo(x + y + 1, N + 1 - 2 * x - 3 * y);
				//cerr << x << " " << y<<" " << t << endl;
				t = (t* cb.pow(2, y)) % MOD;
				t = (t* cb.binom(x + y, y)) % MOD;
				for (int a = 0; a <= A; a++) {
					for (int b = 0; b <= B; b++) {
						int c = x - a - b;
						if (c < 0) {
							break;
						}
						if (c <= C) {
							x1 = (A - a + B - b - C + c) / 2;
							x2 = (A - a - B + b + C - c) / 2;
							x3 = (-A + a + B - b + C - c) / 2;
							if (x1 >= 0 && x2 >= 0 && x3 >= 0) {
								tt = t;
								tt = (tt* cb.fact(x)) % MOD;
								tt = (tt* cb.inv_fact(a)) % MOD;
								tt = (tt* cb.inv_fact(b)) % MOD;
								tt = (tt* cb.inv_fact(c)) % MOD;
								tt = (tt* cb.fact(y)) % MOD;
								tt = (tt* cb.inv_fact(x1)) % MOD;
								tt = (tt* cb.inv_fact(x2)) % MOD;
								tt = (tt* cb.inv_fact(x3)) % MOD;
								//cerr << a << " " << b << "  " << c;
								//cerr << x1 << " " << x2 << "  " << x3;
								//cerr << tt << endl;
								//cerr << endl;
								res = (res + tt) % MOD;
							}
						}
					}
				}
			}
		}
	}
	cout << res << endl;
}
0