すぬけのお誕生日コンテスト D. Subsequence
問題(というかトップページ)
解法
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; }