【CODE FESTIVAL 2016 Grand Final J】123 Pairs
mrsrz
2月 24, 2020
枚举，组合数学。
题目大意：
给定 $1\sim 2n$ 这 $2n$ 个自然数，要求两两配对，共 $n$ 对，并且满足：
- 恰有 $a$ 对整数的差为 $1$。
- 恰有 $b$ 对整数的差为 $2$。
- 恰有 $c$ 对整数的差为 $3$。
保证 $a+b+c=n$。
求不同的匹配方案数，对 $10^9+7$ 取模。
题解：
我们考虑一段连续的数的本质不同的配对方案。
我们用数字表示每组配对的差，并按照起点从左到右排列。那么本质不同的排列只有以下几种：
1，31，333，22，232，2332，……，2333...332，……
也就是说，两个 2 之间可以塞任意多个 3。而 2 必须两组一起配对。所以如果 $b$ 是奇数则方案数为 $0$。
考虑令 $k=\frac b2$。我们考虑将 $n$ 个 3 插入 $k$ 对 2 之间的方案数。由排列组合知识可得方案数为：
我们枚举 333 的个数，再枚举插入到 2 之间的 3 的个数，那么 31 的个数和 1 的个数就唯一确定了。
于是现在要解决的问题是：有四种数，每种数有 $a,b,c,d$ 个，求不同的排列方案数。由排列组合知识可得方案数为：
那么答案就是：
直接求上式的复杂度为 $O(n^2)$。
我们发现下面的式子是卷积的形式：
使用 NTT 快速计算即可。
时间复杂度 $O(n\log n)$。
当然由于这题数据范围小，且模数为 $10^9+7$，所以 NTT 优化完全没有必要。
Code：
#include<cstdio>
typedef long long LL;
const int N=10005,md=1e9+7;
int n,a,b,c,fac[N],iv[N],_[N],ans;
inline int pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
return ret;
}
inline int C(int n,int m){return n>=m?(LL)fac[n]*iv[m]%md*iv[n-m]%md:0;}
int main(){
scanf("%d%d%d%d",&n,&a,&b,&c);
if(b&1){puts("0");return 0;}b>>=1;
for(int i=*fac=1;i<=n*2;++i)fac[i]=(LL)fac[i-1]*i%md;
iv[n*2]=pow(fac[n*2],md-2);
for(int i=n*2-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
for(int i=*_=1;i<=c;++i)_[i]=C(i+b-1,i);
for(int i=0;3*i<=c;++i){
for(int x=c-3*i;~x;--x)if(c-3*i-x<=a){
int _31=c-3*i-x,_1=a-_31;
ans=(ans+(LL)fac[b+i+a]*iv[b]%md*iv[i]%md*iv[_31]%md*iv[_1]%md*_[x])%md;
}
}
printf("%d\n",ans);
return 0;
}