結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー rpy3cpp
提出日時 2017-10-30 20:29:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 2,566 bytes
コンパイル時間 1,591 ms
コンパイル使用メモリ 169,432 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-22 10:54:57
合計ジャッジ時間 2,384 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
constexpr long long mod = 1e9+7;

long long pow_mod(long long b, long long p, long long mod = 1'000'000'007){
    long long ret = 1;
    while (p){
        if (p & 1) ret = (ret * b) % mod;
        b = (b * b) % mod;
        p >>= 1;
    }
    return ret;
}

long long inv_mod(long long n, long long mod = 1'000'000'007){
    return pow_mod(n, mod - 2, mod);
}

class ModuloMath{
private:
    long long N;
    long long mod;
public:
    vector<long long> fac;
    vector<long long> invfac;
    ModuloMath(long long N, long long mod = 1'000'000'007): N{N}, mod{mod}, fac(N + 1, 1), invfac(N + 1, 1){
        for (long long i = 1; i <= N; ++i) fac[i] = (fac[i - 1] * i) % mod;
        invfac[N] = pow_mod(fac[N], mod - 2, mod);
        for (long long i = N; i != 1; --i) invfac[i - 1] = (invfac[i] * i) % mod;
    }
    long long nCr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod * invfac[r] % mod);}
    long long nPr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod);}
    long long nHr(long long n, long long r){return nCr(n + r - 1, r);}
};



long long count_with_fixed_T(int T, int S, int W, int R, int G, int B, ModuloMath & mm){
    long long ans = 0;
    for (int TT = 0; TT <= min(R, T); ++TT){ // TT : 2個ペアとなるRedの個数（RB, RG の個数）
        int gb = T - TT; // GBの個数
        int r1 = R - TT; // 1個のみのRedの個数
        int SS = S - r1; // 1個のみのBlue or Green の個数（g1 + b1）
        if (SS < 0) continue;
        int gg = G - gb;
        int bb = B - gb;
        assert(gg + bb == TT + SS);
        long long pat = mm.nCr(gg + bb, gg);      // GB以外で、Green or Blue が入る gg + bb 個のうち、Green を入れる場所の選び方の総数
        pat = (((((pat * mm.invfac[W]) % mod) * mm.invfac[gb] % mod) * mm.invfac[r1] % mod) * mm.invfac[TT] % mod) * mm.invfac[SS] % mod;
        ans = (ans + pat) % mod;
    }
    ans = (ans * mm.fac[T + S + W] % mod) * pow_mod(2, T) % mod;
    return ans;
}


int solve(int N, int R, int G, int B){
    ModuloMath mm(N + 1);
    int RGB = R + G + B;
    long long ans = 0;
    for (int T = 0; T * 2 <= RGB; ++T){
        int S = RGB - 2 * T;
        int W = N - 3 * T - 2 * S + 1;
        if (W < 0) continue;
        ans = (ans + count_with_fixed_T(T, S, W, R, G, B, mm)) % mod;
    }
    return (int) ans;
}


int main() {
    int N, R, G, B;
    cin >> N >> R >> G >> B;
    cout << solve(N, R, G, B) << endl;
    return 0;
}
0