結果

問題 No.584 赤、緑、青の色塗り
ユーザー tubo28
提出日時 2017-10-26 21:44:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 6,462 bytes
コンパイル時間 701 ms
コンパイル使用メモリ 76,852 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-21 20:47:02
合計ジャッジ時間 1,448 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 6
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define NDEBUG 1
#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
template <int M, unsigned F>
struct mod_int {
constexpr static signed MODULO = M;
constexpr static unsigned MAX_FACT = F;
signed x;
mod_int() : x(0) {}
mod_int(long long y) : x(static_cast<int>(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO)) { }
mod_int(int y) : x(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO) { }
mod_int &operator+=(const mod_int &rhs) {
if ((x += rhs.x) >= MODULO) x -= MODULO;
return *this;
}
mod_int &operator-=(const mod_int &rhs) {
if ((x += MODULO - rhs.x) >= MODULO) x -= MODULO;
return *this;
}
mod_int &operator*=(const mod_int &rhs) {
x = static_cast<int>(1LL * x * rhs.x % MODULO);
return *this;
}
mod_int &operator/=(const mod_int &rhs) {
assert(rhs.x != 0);
x = static_cast<int>((1LL * x * rhs.inv().x) % MODULO);
return *this;
}
mod_int operator-() const { return mod_int(-x); }
mod_int operator+(const mod_int &rhs) const { return mod_int(*this) += rhs; }
mod_int operator-(const mod_int &rhs) const { return mod_int(*this) -= rhs; }
mod_int operator*(const mod_int &rhs) const { return mod_int(*this) *= rhs; }
mod_int operator/(const mod_int &rhs) const { return mod_int(*this) /= rhs; }
bool operator<(const mod_int &rhs) const { return x < rhs.x; }
mod_int inv() const {
signed a = x, b = MODULO, u = 1, v = 0, t;
while (b) {
t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
return mod_int(u);
}
mod_int pow(long long t) const {
assert(!(x == 0 && t == 0));
mod_int e = *this, res = mod_int(1);
for (; t; e *= e, t >>= 1)
if (t & 1) res *= e;
return res;
}
mod_int fact() {
if (_fact[0].x == 0) prepare();
return _fact[x];
}
mod_int inv_fact() {
if (_fact[0].x == 0) prepare();
return _inv_fact[x];
}
mod_int choose(mod_int y) {
assert(y.x <= x);
return this->fact() * y.inv_fact() * mod_int(x - y.x).inv_fact();
}
static mod_int _fact[MAX_FACT + 1];
static mod_int _inv_fact[MAX_FACT + 1];
static void prepare() {
_fact[0] = 1;
for (unsigned i = 1; i <= MAX_FACT; ++i) {
_fact[i] = _fact[i - 1] * int(i);
}
_inv_fact[MAX_FACT] = _fact[MAX_FACT].inv();
for (int i = (int) MAX_FACT - 1; i >= 0; --i) {
_inv_fact[i] = _inv_fact[i + 1] * (i + 1);
}
}
};
template<int M, unsigned F>
std::ostream &operator<<(std::ostream &os, const mod_int<M, F> &rhs) {
return os << rhs.x;
}
template<int M, unsigned F>
std::istream &operator>>(std::istream &is, mod_int<M, F> &rhs) {
long long s;
is >> s;
rhs = mod_int<M, F>(s);
return is;
}
template<int M, unsigned F>
mod_int<M, F> mod_int<M, F>::_fact[MAX_FACT + 1];
template<int M, unsigned F>
mod_int<M, F> mod_int<M, F>::_inv_fact[MAX_FACT + 1];
template<int M, unsigned F>
bool operator == (const mod_int<M, F> &lhs, const mod_int<M, F> &rhs) {
return lhs.x == rhs.x;
}
template<int M, unsigned F>
bool operator != (const mod_int<M, F> &lhs, const mod_int<M, F> &rhs) {
return !(lhs == rhs);
}
const int MF = 3010;
const int MOD = 1000000007;
using mint = mod_int<MOD, MF>;
mint binom(int n, int r) {
return (r < 0 || r > n || n < 0) ? 0 : mint(n).choose(r);
}
mint fact(int n) {
return mint(n).fact();
}
mint inv_fact(int n) {
return mint(n).inv_fact();
}
using namespace std;
// K = R + G + B
// K = 1 + 2 + 2 + 2 + 1 + ...
// f(i) := 2i,1k-2i
// g(i) := R,G,Bi
// ans += f(i)G(i)
using ll = long long;
ll N, R, G, B;
ll K;
ll naive() {
vector<int> a;
if (N < K) return 0;
for (int i = 0; i < N - K; ++i) {
a.push_back(0);
}
for (int i = 0; i < R; ++i) {
a.push_back(1);
}
for (int j = 0; j < G; ++j) {
a.push_back(2);
}
for (int k = 0; k < B; ++k) {
a.push_back(3);
}
int ans = 0;
do {
bool ok = true;
for (int i = 0; i < N - 1; ++i) {
if (a[i] && a[i + 1] && a[i] == a[i + 1]) {
ok = false;
break;
}
if (i + 2 != N && a[i] && a[i + 1] && a[i + 2]) {
ok = false;
break;
}
}
if (ok) {
++ans;
}
} while (next_permutation(a.begin(), a.end()));
return ans;
}
mint pow2[3010];
mint f(ll single, ll pair) {
mint res = 1;
ll space = N - (pair * 2 + single);
if (space < 0) return 0;
res *= binom(single + pair, single);
ll p = single + pair;
ll q = N - (2 * pair + single);
res *= binom(q + 1, p);
return res;
}
mint g(ll single, ll pair) {
mint res = 0;
for (ll r = pair - min(G, B); r <= min({pair, R, G + B}); ++r) {
int single_r = R - r;
int single_g = G - (pair - r);
int single_b = B - (pair - r);
mint x = 1;
x *= binom(pair, r);
x *= binom(single, single_r);
x *= binom(single - single_r + r, single_g);
x *= binom(single - single_r + r - single_g, single_b);
res += x;
}
return res;
}
int solve(int n, int r, int g, int b) {
N = n;
R = r;
G = g;
B = b;
K = R + G + B;
mint ans = 0;
for (int pair = 0; pair * 2 <= K; ++pair) {
ll single = R + G + B - pair * 2;
ans += ::f(single, pair) * ::g(single, pair) * pow2[pair];
}
return ans.x;
}
int main() {
pow2[0] = 1;
for (int i = 1; i < 3010; ++i) {
pow2[i] = pow2[i - 1] * 2;
}
if (false) {
for (int n = 0; n < 30; ++n) {
for (int r = 0; r <= 3; ++r) {
for (int g = 0; g <= 3; ++g) {
for (int b = 0; b <= 3; ++b) {
int res = solve(n, r, g, b);
int exp = naive();
cout << res << ' ' << exp << endl;
assert(res == exp);
}
}
}
}
} else {
int n, r, g, b;
cin >> n >> r >> g >> b;
cout << solve(n, r, g, b) << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0