NKOJ 2966 (BZOJ 3622)已经没什么好害怕的了 (DP+二项式反演)

P2966【2014湖北省队互测week2】已经没什么好害怕的了

问题描述

已经使Modoka有签订契约,和自己一起战斗的想法后,Mami忽然感到自己不再是孤单一人了呢。
于是,之前的谨慎的战斗作风也消失了,在对Charlotte的傀儡使用终曲——Tiro Finale后,Mami面临着即将被Charlotte的本体吃掉的局面。
这时,已经多次面对过Charlotte的Homura告诉了学OI的你这样一个性质——Charlotte的结界中有两种具有能量的元素——一种是“糖果”,另一种是“药片”,每种各有n个。在Charlotte发动进攻前,“糖果”和“药片”会两两配对,若恰好“糖果”比“药片”能量大的组数比“药片”比“糖果”能量大的组数多k组,则在这种局面下,Charlotte的攻击会丢失,从而Mami仍有消灭Charlotte的可能。你必须根据Homura告诉你的“糖果”和“药片”的能量的信息迅速告诉Homura这种情况的个数。

输入格式

第一行两个整数n,k,含义如题目描述。
接着第二行n个整数,第i个数表示第i个糖果的能量。
第三行n个整数,第j个数表示第j个药片的能量。

输出格式

一个整数,表示消灭Charlotte的情况个数。答案可能会很大,所以mod (109+9)

样例输入

4 2
5 35 15 45
40 20 10 30

样例输出

4

数据范围:

约定:给出的2*n个能量值两两不同
对于10%的数据:1<=n<=10
对于40%的数据:1<=n<=500
对于100%的数据:1<=n<=2000,0<=k<=n


先将$A_i$和$B_i$排序
考虑如何计算恰有K对$A_i>B_i$的方案数。

令$F[i]$表示恰有$i$对的方案数,令$f[i][j]$表示$A_i$的前$i$个数有$j$对的方案数。
令$t[i]$表示$B$中小于$A_i$的数的数量。
那么有转移方程$f[i][j]=f[i-1][j]+f[i-1][j-1]*(t[i]-j+1)$,$t[i]-j+1$表示总共有$t[i]$个数可以与$A[i]$匹配,而其中已经匹配了$j-1$个。

然后令$G[i]=(n-i)!f[n][i]$,注意到,这里的$G[i]$意思是先确定$i$对$A_x>B_x$,然后剩下的随便排列。
考虑$G[i]$与$F[i]$的关系,能够推出
$$G[i]=\sum_{j=i}^{n}C_{j}^{i}F[j]$$
这里我们考虑对于$G[i]$,肯定至少有$i$对,但剩下的任意排列可能使得对数增加,同时可能造成重复。因此枚举总共有多少对,然后考虑重复,对于有$j$对的方案,在$G[i]$中被重复算的次数恰好就是$C_{j}^{i}$,意思是从这$j$对中选出$i$对作为一开始在$f[n][i]$中确定的$i$对。

最后二项式反演得到$$F[i]=\sum_{j=i}^{n}(-1)^{j-i}C_{j}^{i}G[j]$$
总时间复杂度$O(n^2)$


代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 2005
#define ll long long
using namespace std;
const ll mod=1e9+9;
ll n,m,A[N],B[N],f[N][N],C[N][N],F[N],G[N],fac[N],t[N];
int main()
{
ll i,j,k;fac[0]=1;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)scanf("%lld",&A[i]);
for(i=1;i<=n;i++)scanf("%lld",&B[i]);
if(n+m&1)return puts("0"),0;
m=(n+m)>>1;
for(i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
for(i=0;i<=n;i++)C[i][0]=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
sort(A+1,A+n+1);
sort(B+1,B+n+1);
for(i=j=1;i<=n;i++)
{
while(j<=n&&A[i]>B[j])j++;
t[i]=j-1;
}
for(i=0;i<=n;i++)f[i][0]=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(0ll,t[i]-j+1)%mod)%mod;
for(i=0;i<=n;i++)G[i]=fac[n-i]*f[n][i]%mod;
for(i=m,k=1;i<=n;i++,k=-k)F[m]+=k*C[i][m]*G[i]%mod,F[m]%=mod;
printf("%lld",(F[m]+mod)%mod);
}