Description

Solution

首先对于要求一个恰好为\(k\)的答案，我们可以转化为不少于\(k\)的答案，然后容斥

怎么求不少于\(k\)的答案呢，我们通常是钦定几个条件必然满足，剩下的就是排列组合乘进去

因为显然会算重，所以要容斥

对于此题：

我们先对两个序列排序

令\(f[i][j]\)表示前第一个序列前\(i\)个数与第二个序列匹配，大于的匹配数不少于\(k\)的方案数

\[ f[i][j]=f[i-1][j]+f[i-1][j-1]*[k-(i-1)] \]

这里的\(k\) 指的是在第二个序列中小于\(a[i]\)的数的个数

显然，仅仅这样是不够的，因为\(f[i][j]\)还要再乘上\((n-i)!\)，表示剩下的数的匹配方案

那么剩下的直接二项式容斥就可以了

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)>(b)?(b):(a))#define reg register#define int llinline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}const int MN=2005,mod=1e9+9;#define Mul(x,y) (1ll*x*y%mod)#define Add(x,y) ((x+y+mod)%mod)int n,k,a[MN],b[MN],c[MN],fac[MN],C[MN][MN],f[MN][MN],ans;signed main(){    n=read();k=read();    reg int i,j;    for(i=1;i<=n;++i) a[i]=read();    for(i=1;i<=n;++i) b[i]=read();    std::sort(a+1,a+n+1);std::sort(b+1,b+n+1);    for(fac[0]=i=1;i<=n;++i)fac[i]=Mul(fac[i-1],i);    C[0][0]=1;    for(i=1;i<=n;++i)    {        C[i][0]=C[i][i]=1;        for(j=1;j
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！