【题解】White, Black and White Again [CF306C]
传送门：( ext{White, Black and White Again}) ( ext{[CF306C]})
【题目描述】
有 (n) 个盒子排成一行，(w) 个互不相同的好球，(b) 个互不相同的坏球，现要将球全部放入盒子中，并满足从左到右依次为：若干好球、若干坏球、若干好球。每个盒子只能放一种类型的球且盒子不能为空。
【分析】
考虑最 (naive) 的想法：依次枚举放好球的盒子数量 (i) 。
将坏球视作一个整体，可以插在好球的中间，有 (i-1) 种方案。
将 (w) 个好球划分到 (i) 个盒子中，相当于一个插板问题，有 (C_{w-1}^{i-1}) 种方案，坏球同理，将 (b) 个坏球划分到 (b-i) 个盒子中，有 (C_{b-1}^{n-i-1}) 种方案。
最后再乘上 (w!) 以及 (b!)，则答案为 (w!b!sum_{i=2}^{n-1}(i-1)C_{w-1}^{i-1}C_{b-1}^{n-i-1}) 。
时间复杂度为 (O(nlog{n})) 或者 (O(n))，已经可以轻松跑过了，现在考虑能不能优化。
先推一波柿子:
由 (mC_{n}^{m}=nC_{n-1}^{m-1}) 得：
改变 (i) 的枚举方式得：
由范德蒙德卷积 (sum_{i=0}^{k} C_{n}^{i} C_{m}^{k-i}=C_{n+m}^{k}) 得：
现在查询变成 (O(1)) 或者 (O(log{n})) 了。
那么这个式子又应该如何理解呢？
由于球的排列方式一定是 “好...好....坏...坏...好...好”，考虑直接将 (w+b) 个球分配到 (n) 个盒子中，即在 (w+b-1) 个空隙中插入 (n-1) 块板子。但由于好坏球之间必定会有 (2) 块固定的板子（由好坏球个数决定，在一次询问中球数是已知的），所以相当于在 (w+b-3) 个空隙中插入 (n-3) 块板子，方案数为 (C_{w+b-3}^{n-3}) 。由于坏球的位置依旧不确定，所以要乘上 (w-1)。最后再乘以 (w!b!) 即为答案。
注意模数别看错了，是 (10^9+9) 不是 (10^9+7)，( ext{CF}) 总喜欢搞一些近似模数来坑你。
【Code】
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4003,P=1e9+9;
int n,w,b,jc[N<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return x==0?1:mi(x,P-2);}
inline int C(Re m,Re n){return (LL)jc[n]*inv(jc[n-m])%P*inv(jc[m])%P;}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(w),in(b),jc[0]=1;
for(Re i=1;i<=w+b;++i)jc[i]=(LL)jc[i-1]*i%P;
// Re ans=0;
// for(Re i=max(n-b,2);i<=n-1&&i<=w;++i)
// (ans+=(LL)C(i-1,w-1)*C(n-i-1,b-1)%P*(i-1)%P)%=P;
// printf("%d
",(LL)ans*jc[w]%P*jc[b]%P);
printf("%d
",(LL)C(n-3,w+b-3)*(w-1)%P*jc[w]%P*jc[b]%P);
}