結果

問題 No.584 赤、緑、青の色塗り
ユーザー legendcn
提出日時 2025-05-04 15:34:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,483 ms / 2,000 ms
コード長 1,611 bytes
コンパイル時間 2,046 ms
コンパイル使用メモリ 194,000 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-04 15:34:09
合計ジャッジ時間 5,556 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
# define int long long 
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
# define endl "\n"
const int N = 6005, mod = 1000000007;

int n, r, g, b;
int quick_pow (int a, int b = mod - 2)
{
	int ans = 1;
	while (b)
	{
		if (b & 1)
			ans = 1ll * ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}
int mul[N], inv[N];
void init ()
{
	mul[0] = 1;
	for (int i = 1; i < N; i ++ )
		mul[i] = 1ll * mul[i - 1] * i % mod;
	inv[N - 1] = quick_pow (mul[N - 1]);
	for (int i = N - 2; i >= 0; i -- )
		inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
int C (int n, int m)
{
	return n < m ? 0 : mul[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main ()
{
    // freopen ("RGB.in", "r", stdin); freopen ("RGB.out", "w", stdout);
    init ();
	cin >> n >> r >> g >> b;
	if (r > g) swap (r, g);
	if (r > b) swap (r, b);
	if (g > b) swap (g, b);
	int ans = 0, pw = 1;
	for (int S2 = 0; 2 * S2 <= r + g + b; S2 ++ )
	{
		int S1 = r + g + b - 2 * S2;
		int res = 0;
		for (int i = 0; i <= min (S2, r); i ++ )
		{
			for (int j = 0; j <= min (S2, g); j ++ )
			{
				int k = 2 * S2 - i - j;
				if (0 <= k && k <= b)
				{
					int a = S2 - i, b = S2 - j, c = S2 - k;
					res = 1ll * (res + 1ll * C (S2, a) * C (S2 - a, b) % mod * 
						1ll * C (S1, r - i) % mod * C (S1 - r + i, g - j)) % mod;
				}
			}
		}
		ans = (ans + 1ll * res * 
			C (n + 1 - S2 * 2 - S1, S2) % mod * 
			C (n + 1 - S2 * 3 - S1, S1) % mod * pw) % mod;
		pw = 1ll * pw * 2 % mod;
	}
	cout << ans << endl;
	return 0;
}
0