CF306C

简单的组合数学。

1. 题意

给出 $n$ 天，以及互不相同的 $w$ 件好事、$b$ 件坏事，每天只能出现好事、坏事中的一种，要求发生的顺序为 好事 - 坏事 - 好事 的情况的方案数，答案对 $10^9+9$ 取模。

2. 思路

首先，互不相同可以直接转化为相同，也就是我们可以现将答案算出来，然后乘上 $w!\cdot b!$ 即可。

我们再来想如果处理相同的。

我们发现，当好事的总天数一定的时候，前面有多少个、后面有多少个其实是不影响答案的，因为前面不管有多少个，其实都是一样的。

所以，我们可以统计 好事 - 坏事 的情况，然后对于每一个好事天数一定的，我们将一些好事的天放在坏事后面，就可以满足答案了。

答案将会乘上好事的天数减 1。

现在思路已经比较明显了：我们直接暴力枚举好事的天数 $x$，那么坏事的天数就是 $n-x$。

然后，我们发现，要将 $w$ 个好事放入 $x$ 天，每天至少一个，所以方案数就为 $\binom{w-1}{x-1}$。

坏事同理。

预处理组合数可以用 $O(n)$ 预处理阶乘及其逆元，不过没必要，直接 $O(n^2)$ 就可以了。

3. Code

注意要处理两倍的大小。

int main()
{
    init();
    cin >> n >> w >> b;
    int ans = 0;
    for (int gday = 1; gday < n; ++ gday)//枚举好事的天数
        ans = (ans + (gday - 1ll) * C[w - 1][gday - 1] % Mod * C[b - 1][n - gday - 1] % Mod) % Mod;
    cout << 1ll * ans * fact[w] % Mod * fact[b] % Mod << endl;
    return 0;
}