mayoko’s diary

プロコンとかいろいろ。

すぬけのお誕生日コンテスト D. Subsequence

問題(というかトップページ)

snuke21.contest.atcoder.jp

解法

t を作って, そこから s を作ることを考えます。

例えば t が 11001 とかだったとすると, s は, (0...0)1(0...0)1(1...1)0(1...1)0(0...0)1(適当な文字列)
というようにして構成できます。t[i] = '0' だったら, t[i-1] と t[i] の間は '1' を適当に埋め込み, t[i] = '1' だったら t[i-1] と t[i] の間には '0' を埋め込むということです。

この規則は, t がどのような文字列で合っても, 当てはめ方は同じなので, (t の並べ方) * (各 t に対して, s の並べ方) が答えになります。s の並べ方は, t で既に使った分を引いて, 残りの 0, 1 の並べ方は (0 を d グループに分ける場合の数) * (1 を c グループに分ける場合の数) * (残りの 0, 1 を並べる場合の数)です。すべて combination を求めておけば O(1) で求められます。

const ll MOD = 1e9+7;
const int MAXN = 2222;
ll comb[2*MAXN][2*MAXN];

ll calc(int sum, int num) {
    if (num == 0) {
        if (sum == 0) return 1;
        else return 0;
    }
    return comb[sum+num-1][sum];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 2*MAXN; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            comb[i][j] %= MOD;
        }
    }
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    ll ans = 0;
    A -= C;
    B -= D;
    for (int a = 0; a <= A; a++) for (int b = 0; b <= B; b++) {
        ll tmp = calc(a, D);
        (tmp *= calc(b, C)) %= MOD;
        int aa = A-a, bb = B-b;
        (tmp *= comb[aa+bb][aa]) %= MOD;
        ans += tmp;
    }
    ans %= MOD;
    (ans *= comb[C+D][C]) %= MOD;
    cout << ans << endl;
    return 0;
}