【BZOJ3622】已经没有什么好害怕的了

时间:2022-09-03 00:01:14

题面

题目描述

已经使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;
}