yukicoder No.584 - 赤、緑、青の色塗り

問題

No.584 赤、緑、青の色塗り - yukicoder

問題概要

一直線にNマスが並んでいる。各マスを赤、緑、青いずれかの色で塗ることが出来る。塗らないマスがあっても良い。マスを塗る条件として、

• 同じ色は隣接してはいけない
• 異なる色であれば連続する2マスを塗ってもよい
• 連続する3以上のマスを塗ることは出来ない

がある。赤、緑、青の色で塗らなければならないマスがちょうど個ある時、マスの塗り方は何通りあるか、で割った余りを答えよ。

• 
• 

アイデア

色が入ったマスの塊としては、1個と2個の2種類しかありえない。2個の塊を個作るとすると、1個の塊は、色をぬるマスの個数は個なので個になる。

さらに、2個の塊には、色の組み合わせとしてrg,gb,brの3通りがある。2個の塊のために、赤を個使うことにすると、gbの塊は個必要になる。また、残った赤(個)は1個の塊に必ず使うことになる。

この時点で、緑は個、青は個残っている。まだ色が決まっていない枠には、この2色のどちらかしか入る余地が無いので、それが何通りあるかを求める事ができる。

以上より、とを全探索して全ての組み合わせが求められる()。細かい組み合わせの計算方法はコード参照。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const ll mod = 1000000007;

ll mod_pow(ll x, ll n){
    ll ret = 1;
    while(n){
        if(n&1) (ret*=x)%=mod;
        (x*=x)%=mod;
        n>>=1;
    }
    return ret;
}

ll mod_inv(ll x){
    return mod_pow(x, mod-2);
}

const int N = 6006;
ll f[N];
ll C(ll n, ll r){
    if(n<r) return 0;
    ll ret = f[n];
    (ret*=mod_inv(f[r]))%=mod;
    (ret*=mod_inv(f[n-r]))%=mod;
    return ret;
}

ll solve(){
    int n,r,g,b;
    cin >>n >>r >>g >>b;
    int S = r+g+b;

    if(S==0) return 1;
    if(S>n) return 0;

    ll ans = 0;
    // 2個の塊の個数
    rep(i,S){
        // 1個の塊の個数
        int O = S - 2*i;
        if(O<0) continue;
        // 最低でも必要な空白
        int sp = i+O-1;
        if(2*i + O + sp > n) continue;

        // 自由に挿入できる空白の個数
        int rsp = n - (2*i+O+sp);

        // 1個の塊と2個の塊の枠の配置方法
        ll t = C(i+O,i);
        // 残った空白の挿入方法
        (t *= C(i+O+rsp,rsp)) %= mod;
        // 2個の塊は、各セルごとに入れ替えられる
        (t *= mod_pow(2,i)) %= mod;

        rep(j,i+1){
            int rem_r = r-j;
            if(rem_r<0) continue;
            if(rem_r>O) continue;

            ll tt = t;
            // 2個の塊に赤を割り当てる
            (tt *= C(i,j)) %= mod;
            // 1個の塊に赤を割り当てる
            (tt *= C(O,rem_r)) %= mod;

            int rem_g = g-(i-j), rem_b = b-(i-j);
            if(rem_g<0 || rem_b<0) continue;
            // 残りのマスに2色を割り当てる
            (tt *= C(rem_g+rem_b,rem_g)) %= mod;

            (ans += tt) %= mod;
        }
    }
    return ans;
}

int main(){
    f[0] = 1;
    for(int i=1; i<N; ++i) f[i] = (f[i-1]*i)%mod;

    cout << solve() << endl;
    return 0;
}