赤、緑、青の色塗り [yukicoder No.584] - はまやんはまやんはまやん

解法

組合せ計算をする。
塗り方を考えると1色のグループと2色のグループに分かれる。
2色のグループのtwo個と、2色のグループに赤を配置する個数r個を全探索する。

2色のグループをtwo個とすると、1色のグループone個は、one=R+G+B-two*2である。
2色のグループに赤を配置する個数r個とすると、残りの2色のグループには緑青のペアとなる。
つまり、1色のグループと赤の相方となる緑はG-(two-r)個で、青はB-(two-r)個である。

配置の組合せ
aCb(one + two, two) * nHk(N-two*2-one-two-one+1, one+two+1)
aCb(one + two, two) : 色のグループの組み合わせ数
nHk(N-two*2-one-two-one+1, one+two+1) : 間に入れる空白の組み合わせ数
　
配色の組合せ
com.aCb(two, r) * (mint(2) ^ two) * com.aCb(one, R - r) * com.aCb(r + one - (R - r), G - (two - r))
com.aCb(two, r) : 2つのグループの赤の配置の組合せ
(mint(2) ^ two) : 2つのグループのそれぞれの組合せ
com.aCb(one, R - r) : 1つのグループでの赤の配置の組合せ
com.aCb(r + one - (R - r), G - (two - r)) : 1つのグループと赤のペアとなる2つのグループの緑の配置の組合せ

int N, R, G, B;
Comb<mint, 10101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> R >> G >> B;

    mint ans = 0;
    rep(two, 0, N) rep(r, 0, min(R, two) + 1) {
        int one = R + G + B - two * 2;
        int mi = two * 3 - 1 + one * 2;

        if (N < mi or one < 0 or min(G, B) < two - r) continue;

        int rest = N - two * 2 - one - two - one + 1;
        int all = one + two + 1;

        mint place = com.aCb(one + two, two) * com.nHk(all, rest);
        mint color = com.aCb(two, r) * (mint(2) ^ two);
        color *= com.aCb(one, R - r);
        color *= com.aCb(r + one - (R - r), G - (two - r));

        ans += place * color;
    }
    cout << ans << endl;
}