結果
問題 |
No.584 赤、緑、青の色塗り
|
ユーザー |
|
提出日時 | 2025-04-26 23:21:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,731 ms / 2,000 ms |
コード長 | 2,541 bytes |
コンパイル時間 | 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 |
ソースコード
#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*/