题面

题目描述

已经使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%的数据：l<=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];\)

用这种方法，我们可以处理出每一项的容斥系数，然后进行容斥即可。

代码如下:

#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;
}

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

原文：https://www.cnblogs.com/Emiya-wjk/p/9986667.html