[BZOJ3622]已经没有什么好害怕的了（容斥原理+DP）-CSDN博客

本文链接：https://blog.csdn.net/Blue_CuSO4/article/details/80990960

题目：

题解：

首先列个方程可以看出如果要求糖果比药品多k组的每组有多少个，其中糖果就是 ${n+k\over 2}$ ，那么如果这个数字不是个整数就GG

这样恰好k个不是很好直接求，我们考虑求至少有k个，设f[i][j]表示前i组中至少有j组糖果比药片大，设nxt[i]表示药片中比a[i]小的数量，那么我们可以列出DP式子 $f[i][j]=f[i-1][j]+f[i-1][j-1]*max(0,nxt[i]-(j-1))$

那么这个比a[i]小的数量可以排序之后求。但是那些随便放的数字也可能会造成A比B大的情况，所以需要容斥一下

容斥原理有言曰：至少有k个的-C(k+1,k)* 至少有k+1个的+C(k+2,k) *至少有k+2个的…=恰好有k个的

那么我们直接按照这个做就好啦

代码：

代码引自ATP学姐QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long Mod=1e9+9;
int n,k,a[2010],b[2010];
long long Ans,f[2010][2010],C[2010][2010],mul[2010];
void get_C(int N){
    for (int i=0;i<=N;i++) C[i][0]=1;
    for (int i=1;i<=N;i++)
      for (int j=1;j<=i;j++)
        C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
}
int main()
{
    scanf("%d%d",&n,&k);
    if ((n+k)%2!=0){printf("0\n");return 0;}
    k=(n+k)/2;f[0][0]=1;
    get_C(n);mul[0]=1;
    for (int i=1;i<=n;i++) mul[i]=mul[i-1]*i%Mod;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    sort(a+1,a+n+1);sort(b+1,b+n+1);
    for (int i=0,p=0;i<=n;i++){
        while (p<n&&b[p+1]<a[i+1]) ++p;
        for (int j=0;j<=i;j++)
          if (f[i][j]!=0){
              f[i+1][j]=(f[i+1][j]+f[i][j])%Mod;
              if (p-j>=0)
                f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(long long)(p-j)%Mod)%Mod;
          }
    }
    for (int i=0;i<=n;i++) f[n][i]=f[n][i]*mul[n-i]%Mod;
    for (int i=k,dlt=1;i<=n;i++,dlt=-dlt)
      Ans=(Ans+dlt*C[i][k]*f[n][i]%Mod)%Mod;
    Ans=(Ans+Mod)%Mod;
    printf("%I64d\n",Ans);
    return 0;
}