洛谷 U141583 命运

洛谷 U141583 命运

洛谷传送门

题目背景

由于SeawaySeawaySeaway最近的运气实在有些差，伟大的命运之神决定眷顾他，让他的生活有一些盼头而不至于第二天就上吊死掉。

题目描述

对于SeawaySeawaySeaway来讲，生活中的一切事除了好事就是坏事。现在，SeawaySeawaySeaway的生活状态是：坏事->坏事->坏事->坏事。显然，SeawaySeawaySeaway很悲催。所以他得到了命运之神的怜悯。但是神是公正的，他不会因为SeawaySeawaySeaway这样惨就把SeawaySeawaySeaway的生活状态全都变成好事。命运之神想出了一个折中的办法：把SeawaySeawaySeaway的生活状态变成好事->坏事->好事。他大发神威，并把这个结果告诉了SeawaySeawaySeaway。

同时，他好神做到底，他一并告诉了SeawaySeawaySeaway他接下来的安排：对于SeawaySeawaySeaway接下来的NNN天，会发生aaa件互不相同的好事和bbb件互不相同的坏事。每天至少发生一件事，且要么全发生好事，要么全发生坏事。这NNN天符合SeawaySeawaySeaway改变后的生活状态。

现在，SeawaySeawaySeaway想知道，这些事件发生的方案数。两种方案不同，当且仅当两种方案事件发生顺序有所不同。需要注意的是，一天中发生的事件也有顺序上的差别。

输入格式

一行三个整数，代表N,a,bN,a,bN,a,b。意义如题目描述所示。

输出格式

一行一个整数，表示方案数对109+910^9+9109+9取模的结果。

---

命题背景：

希望Seaway的运气能够快快好起来。

不要一直这么丧

要像枫哥那样

来个漂漂亮亮的翻盘~

题解：

重温一下经典的组合数的问题。

代码：

#include<cstdio>
#define ll long long
#define mod 1000000009
using namespace std;
const int maxn=4001;
int fac[maxn],inv[maxn];
int n,w,b,ans;
void init_fact()
{
    fac[0]=1;
    for(int i=1;i<=maxn;i++)
        fac[i]=(ll)i*fac[i-1]%mod;
}
void init_inv()
{
    inv[0]=1;inv[1]=1;
    for(int i=2;i<=maxn;i++)
        inv[i]=mod-(ll)(mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=maxn;i++)
        inv[i]=(ll)inv[i-1]*inv[i]%mod;
}
int calc(int n,int m)
{
    return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
    init_fact();
    init_inv();
    scanf("%d%d%d",&n,&w,&b);
    for(int i=1;i<=b;i++)
        if(n-i>=2 && n-i<=w)
            ans=((ll)ans+(ll)(n-i-1)*calc(b-1,i-1)%mod*calc(w-1,n-i-1)%mod)%mod;
    ans=(ll)((ll)ans*fac[w]%mod*fac[b]%mod)%mod;
    printf("%d",ans);
    return 0;
}