[BZOJ3622] 已经没有什么好害怕的了
给定两个长度都为n的数列a和b,保证所有数互不相同,求有多少配对\((a,b)\)的方案,使得\((a>b)=(a<b)+k\)。
试题分析
由题目可以得到前者的数量\(c=\frac{n+k}{2}\)。
由于两种情况都考虑的时候我们没有办法记录哪些数选过,哪些数没选。
干脆直接撇开一种情况,去看另外一种情况。
那么我们设\(f_{i,j}\)表示考虑到\(a_1,a_2,\ldots a_n\),钦点了\(j\)个数\((a_k>b_k)\)的方案数。
可以得到转移:\[f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times (right_i -(j-1))\]
其中\(right_i\)最大的\(b_{right_i}\)使得\(a_i>b_{right_i}\)。
那么至少选\(j\)个的方案数也就是\(f_{n,j}\times (n-j)!\)。
设\(g_i\)为正好选择\(i\)个的方案数。
那么考虑一个\(g_i\)在\(g_j (j>i)\)中被统计了多少次。
对于每一个\(g_i\)的方案集合\(\{ x\}\),都会被上面算到\(\binom{j}{i}\)次。
那么可以得到式子:\(g_i=f_{n,i}\times (n-i)! - \sum_{i< k\leq n} \binom{j}{i} g_j\)。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
inline LL read(){
LL x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const LL INF = 2147483600;
const LL MAXN = 100010;
const LL Mod = 1000000009;
LL f[2001][2001]; LL N,K;
LL Pow[2001]; LL fac[MAXN+1],ifac[MAXN+1],inv[MAXN+1];
inline LL C(LL n,LL m){
if(n==m) return 1; if(!m) return 1;
//printf("ifac[%lld] = %lld ifac[%lld] = %lld fac[%lld] = %lld\n",n-m,ifac[n-m],m,ifac[m],n,fac[n]);
return fac[n]*ifac[m]%Mod*ifac[n-m]%Mod;
}
LL a[MAXN+1],b[MAXN+1],g[MAXN+1];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
N=read(),K=read(); K=(N+K)>>1;
inv[1]=1; fac[1]=1; ifac[1]=1; fac[0]=1; ifac[0]=1;
for(LL i=2;i<=N;i++) fac[i]=fac[i-1]*i%Mod;
for(LL i=2;i<=N;i++) inv[i]=(Mod-(Mod/i)*inv[Mod%i])%Mod;
for(LL i=2;i<=N;i++) ifac[i]=ifac[i-1]*inv[i]%Mod;
for(LL i=1;i<=N;i++) a[i]=read();
for(LL i=1;i<=N;i++) b[i]=read();
sort(a+1,a+N+1); sort(b+1,b+N+1); f[0][0]=1;
for(LL i=1;i<=N;i++){
LL rg=lower_bound(b+1,b+N+1,a[i])-b-1;
for(LL j=0;j<=i;j++){
if(j&&rg>=(j-1)) f[i][j]+=f[i-1][j-1]*(rg-(j-1))%Mod;
f[i][j]+=f[i-1][j]; f[i][j]%=Mod; f[i][j]=(f[i][j]%Mod+Mod)%Mod;
}
}
for(LL i=N;i>=K;i--){
g[i]=f[N][i]*fac[N-i]%Mod;
for(LL j=i+1;j<=N;j++)
g[i]=(g[i]-C(j,i)*g[j]%Mod+Mod)%Mod;
} printf("%lld\n",g[K]);
return 0;
}