結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー legendcn
提出日時 2025-05-04 15:54:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 2,071 bytes
コンパイル時間 2,235 ms
コンパイル使用メモリ 193,668 KB
実行使用メモリ 73,884 KB
最終ジャッジ日時 2025-05-04 15:54:52
合計ジャッジ時間 3,631 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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 = 3005, 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 C[N][N];
void init ()
{
	C[0][0] = 1;
	for (int S2 = 1; S2 < N; S2 ++ )
	{
		C[S2][0] = C[S2 - 1][0];
		for (int r2 = 1; r2 <= S2; r2 ++ )
			C[S2][r2] = (C[S2 - 1][r2] + C[S2 - 1][r2 - 1]) % mod;
	}

}
void solve ()
{
    init ();
    cin >> n >> R >> G >> B;
    int ans = 0;
    for (int S2 = 0; S2 <= n; S2 ++ )
    {
        if (S2 * 2 > R + G + B)
        	break;
        for (int r2 = 0; r2 <= min (S2, R); r2 ++ )
        {
            int lft = S2 - r2;
            if (lft > min (G, B))
            	continue;
            int rg = G - lft;
            int rb = B - lft;
            if (rg < 0 || rb < 0)
            	continue;
            int tmp = 1;
            int ri = R + G + B - 2 * S2;
            int want = ri;
            int need = 2 * want + 3 * S2 - 1;
            if (need > n)
            	continue;
            int can = n - need;
            tmp = tmp * C[S2][r2] % mod;
            tmp = tmp * C[can + S2 + want][can] % mod;
            tmp = tmp * C[S2 + want][S2] % mod;
            tmp = tmp * quick_pow (2, S2) % mod;
            tmp = tmp * C[want][R - r2] % mod;
            tmp = tmp * C[rg + rb][rg] % mod;
            ans = (ans + tmp) % mod;
        }
    }
    cout << ans % mod << endl;
}
signed main ()
{
    // freopen ("RGB.in", "r", stdin); freopen ("RGB.out", "w", stdout);
    double t1 = clock ();
    ios::sync_with_stdio (0); cin.tie (0); cout.tie (0);
    int T = 1;
    // cin >> T;
    while (T -- )
    {
        solve ();
        cout.flush ();
    }
    double t2 = clock ();
    // cerr << "used time: " << (double)(t2 - t1) / (double)CLOCKS_PER_SEC << endl;
    return 0;
}
0