結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー jackzhang
提出日時 2025-04-26 23:21:14
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,731 ms / 2,000 ms
コード長 2,541 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,149 ms
コンパイル使用メモリ 196,852 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-26 23:21:19
合計ジャッジ時間 5,024 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define int long long
const int N = 3005;
const int Mod = 1e9 + 7;
using namespace std;
int n, R, G, B;
int fac[N], ifac[N];
int qpow(int a, int b)
{
    int res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = res * a;
            res %= Mod;
        }
        a = a * a;
        a %= Mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fac[i] = fac[i - 1] * i;
        fac[i] %= Mod;
    }
    ifac[N - 1] = qpow(fac[N - 1], Mod - 2);
    for (int i = N - 2; i >= 0; i--)
    {
        ifac[i] = ifac[i + 1] * (i + 1);
        ifac[i] %= Mod;
    }
}
int A(int n, int m)
{
    if (m < 0 || m > n)
    {
        return 0;
    }
    return fac[n] * ifac[m] % Mod;
}
int C(int n, int m)
{
    if (m < 0 || m > n)
    {
        return 0;
    }
    return fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}
int H(int n, int m)
{
    if (n == 0 && m == 0)
    {
        return 1;
    }
    return C(n - 1, m - 1);
}
signed main()
{
    init();
    cin >> n >> R >> G >> B;
    int colors = R + G + B;
    int cnt = 0;
    for (int two = 0; two <= colors / 2; two++) // 两个组的数量
    {
        int one = colors - two * 2;      // 一个组的数量
        int use = two * 3 + one * 2 - 1; // 使用的格子数量
        if (use > n)                     // 使用的格子超限
        {
            continue;
        }
        // 组中的红色数量
        for (int r = 0; r <= min(R, two); r++)
        {
            if (min(G, B) < two - r) // 剩余绿蓝填不满
            {
                continue;
            }
            // 剩余空白个数
            int empties = n - two * 2 - one;
            // 需有空白个数
            int zone = two + one + 1;
            int placecnt = C(two + one, one) * H(empties + 2, zone) % Mod;
            // 组别分配 * 空白分配
            int redcnt = C(two, r) * C(one, R - r) % Mod;
            // 把红分给两个组 * 把剩下的红分给一个组
            int greencnt = C(r + one - (R - r), G - (two - r)) % Mod;
            // C(两个组中需要匹配的 + 剩下的一个组, 绿色总数 - 两个组用掉的)
            cerr << placecnt << ' ' << redcnt << ' ' << greencnt << endl;
            cnt += placecnt * redcnt % Mod * greencnt % Mod * qpow(2, two) % Mod;
            // 位置总数 * 红色总数 * 绿色总数 * 前后交换
            cnt %= Mod;
        }
    }
    cout << cnt;
    return 0;
}
/*
3 2
3 8
3 0
3 8*/
0