CODE FESTIVAL 2016 Grand Final: J - 123 Pairs

問題概要

から までの 個の数を つずつ 個のペアにするとき，差が のペアが 個，差が のペアが 個，差が のペアが 個あるようなペアの作り方は何通りあるか。

(問題文は https://atcoder.jp/contests/cf16-exhibition-final/tasks/cf16_exhibition_final_j に記載されている。)

制約

• 
• 
• 

アイディア

まず，差が のペアと差が のペアは共に偶奇の異なる数同士がペアになるため，偶奇の一致する数同士がペアになることになる差が のペアは偶数個である必要がある。つまり の場合答えは となる。

以下 の場合のみを考え， とする。

実は，このようなペアの作り方は以下の 種類のペアの組み合わせの並び替えで構成される。

1. 差が のペア つが組み合わさっている。 (例: 1 - 4, 2 - 5, 3 - 6 )
2. 差が のペア つの間に差が のペアが つ挟まっている。(例: 1 - 4, 2 - 3 )
3. 差が のペア つの間に差が のペアが 個以上挟まっている。(例: 1 - 3, 2 - 5, 4 - 7, 6 - 8 )
4. 差が のペア単独 。(例: 1 - 2 )

差が であるような 個のペアのうち，タイプ とタイプ の構成に関わるペアの個数をそれぞれ とする。 このとき，タイプ ，タイプ，タイプ ，タイプのペアの組み合わせはそれぞれである。よってペアの組み合わせの並び替え方は であり， 個のペアのタイプ への割り振り方は， 個の石と 個の仕切りを並べることを考えて であるので で求められる。 あとは考えられる をすべて試せばよい。

実装

二項係数をメモ化再帰で実装すると楽かもしれない。

「 個の石と 個の仕切りを並べることを考えて」の部分で地味にバグらせやすいので注意。

コード

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
const ll MOD = (ll)(1e9+7);

ll memo[5050][5050];
bool done[5050][5050];

ll comb(int n, int k){
    if(n < k){
        return 0ll;
    }
    if(done[n][k]){
        return memo[n][k];
    }
    done[n][k] = true;
    if(k==0 || k==n){
        return memo[n][k] = 1ll;
    }
    memo[n][k] = (comb(n-1,k-1)+comb(n-1,k))%MOD;
    return memo[n][k];
}

int main(void){
    int N,A,B,C,b,x,y,z,m;
    ll ans=0ll,tmp;
    cin >> N >> A >> B >> C;
    if(B&1){
        cout << 0 << endl;
        return 0;
    }
    b = B>>1;
    for(x=0; x*3<=C; ++x){
        m = min(A,C-x*3);
        for(y=0; y<=m; ++y){
            z = C - x*3 - y;
            tmp = comb(A+b+x,x);
            tmp *= comb(A+b,b); tmp %= MOD;
            tmp *= comb(A,y); tmp %= MOD;
            if(b){
                tmp *= comb(z+b-1,z); tmp %= MOD;
            }else if(z){
                tmp = 0ll;
            }
            ans += tmp; ans %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

(提出したものはこちら)

感想

急に解法が降ってきて嬉しかったので共有しておきます。