题面
题目描述
已经使Modoka有签订契约,和自己一起战斗的想法后,Mami忽然感到自己不再是孤单一人了呢。
于是,之前的谨慎的战斗作风也消失了,在对Charlotte的傀儡使用终曲——Tiro Finale后,
Mami面临着即将被Charlotte的本体吃掉的局面。
这时,已经多次面对过Charlotte的Honiura告诉了学OI的你这样一个性质:
Charlotte的结界中有两种具有能量的元素,一种是“糖果”,另一种是“药片”,各有n个。
在Charlotte发动进攻前,“糖果”和“药片”会两两配对,
若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多k组,
则在这种局面下,Charlotte的攻击会丟失,从而Mami仍有消灭Charlotte的可能。
你必须根据Homura告诉你的“糖果”和“药片”的能量的信息迅速告诉Homura这种情况的个数.
输入输出格式
输入格式:
第一行两个整数n,k,含义如题目所描述。
接下来一行n个整数,第i个数表示第i个糖果的能量。
接下来n个整数,第j个数表示第j个药片的能量。
保证上面两行不会有重复的数字
输出格式:
一个答案,表示消灭Charlotte的情况个数,要 mod (10^9 + 9)
输入输出样例
输入样例:
4 2
5 35 15 45
40 20 10 30
输出样例:
4
说明
【样例解释】
正确的组合为:
(5-40,35-20,15-10,45-30),
(5-40,45-20,15-10,35-30),
(45-40,5-20,15-10,35-30),
(45-40,35-20,15-10,5-30)。
【数据范围】
对于100%的数据:1<=n<=2000,0<=k<=n
题目分析
emm说实话,我也不是很懂为什么会想到用DP+容斥,我这里只讲讲,如果你想到了,之后该怎么做。
先进行预处理,求出需满足糖果>药片的最小组数\(lim\),并把两数组从小到大排序,
为了方便起见,我们把糖果设为\(a\),药片设为\(b\)。
我们设转移方程\(f[i][j]\)表示,前\(i\)个糖果与后面的任意药片配对,至少有\(j\)对满足糖果>药片的方案数。
可得出转移方程:\(f[i][j]=f[i-1][j]+f[i-1][j-1]* (k-(j-1));\)
其中,\(k\)表示满足\(lower\_bound(b,a[i])-1\),及第\(i\)种糖果可以配上的药片数。
于是,我们可以把方程理解为:
要想前\(i\)个糖果配上\(j\)对,要么前\(i-1\)种已经配了\(j\)对,第\(i\)种随便配;
要么前\(i-1\)种只配了\(j-1\)对,第\(i\)种需要在剩下的\(k-(j-1)\)个药片中任选一个配对。
这时候就体现出了排序的作用,
给\(b\)数组排序可以方便计算\(k\)的值,给\(a\)数组排序,
则使\(k\)一定单调不下降,所以可以用\(k-(j-1)\)表示可用药片。
由于我们方程只是限定了其中\(j\)对,剩下的均可随意匹配,所以在计算答案时,需乘上\((n-j)!\)。
也正因剩下的可随意匹配,最终结果可能\(>j\)。这时候,就需要我们使用容斥去重。
我也不是很懂为什么dalao都可以看出容斥系数是\((-1)^{i-lim}* C_i^{lim}\),
我就讲讲一个比较朴素的\(O(n^2)\)推系数的方法。
我们设容斥系数为\(g\),显然有\(g[lim]=1\)。
对于\(g[i],i>lim\),它会被第\(lim\)至第\(i-1\)种情况算重。
其中,会被第\(x\)种情况多算\(g[x]* C_i^x\)次。
(在选择的\(i\)个数中选出\(x\)个,方案为\(C_i^x\),每种方案都算了\(g[x]\)次)
以此列出容斥系数方程:\(g[i]-=g[j] *c[i][j];\)
用这种方法,我们可以处理出每一项的容斥系数,然后进行容斥即可。
P.S:
最近才学了二项式反演,发现这道题其实就是二项式反演的模板。
我们用\(f[i]\)表示\(f[n][i]\),设\(g[i]\)表示匹配数刚好等于\(i\)的情况数。
则易得:\(f[k]=\sum\limits_{i=k}^n\lgroup_k^i\rgroup*g[i]\)
进行反演变为:\(g[k]=\sum\limits_{i=k}^n(-1)^{i-k}*\lgroup_k^i\rgroup*f[i]\)
直接计算\(g[lim]\)即可。
代码实现
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=2005,mod=1e9+9;
using namespace std;
inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
LL c[N][N],f[N][N];
LL fac[N],ans;
LL a[N],b[N],g[N];
int main(){
LL n=Getint(),K=Getint();
for(int i=1;i<=n;i++)a[i]=Getint();
for(int i=1;i<=n;i++)b[i]=Getint();
K=(n+K)>>1;
sort(a+1,a+1+n),sort(b+1,b+1+n);
for(int i=0;i<=n;c[i++][0]=1)//预处理组合数
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
f[0][0]=1;
for(int i=1;i<=n;i++){
int k=(lower_bound(b+1,b+1+n,a[i])-b)-1;
for(int j=0;j<=n;j++){
f[i][j]=f[i-1][j];
if(j)f[i][j]=(f[i][j]+f[i-1][j-1]*max(k-j+1,0))%mod;
}
}
fac[0]=fac[1]=1;
for(int i=2;i<=n;i++)fac[i]=fac[i-1]*i%mod;
g[K]=1;
for(int i=K+1;i<=n;i++)//求出容斥系数
for(int j=K;j<i;j++)
g[i]=(g[i]-g[j]*c[i][j])%mod;
for(int i=K;i<=n;i++)ans=(ans+g[i]*(f[n][i]*fac[n-i]%mod)%mod+mod)%mod;
cout<<ans;
return 0;
}