結果

問題 No.584 赤、緑、青の色塗り
ユーザー jackzhang
提出日時 2025-04-26 23:15:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,466 bytes
コンパイル時間 1,948 ms
コンパイル使用メモリ 196,124 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-26 23:16:03
合計ジャッジ時間 4,934 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5 WA * 1
other AC * 4 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #

#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 * qpow(2, 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;
            cnt %= Mod;
        }
    }
    cout << cnt;
    return 0;
}
0