正题

题目链接:https://www.luogu.com.cn/problem/P4859

题目大意

两个长度为\(n\)的序列\(a,b\)两两匹配，求\(a_i>b_i\)的组数比\(a_i<b_i\)的组数多\(k\)的方案数。

保证输入数字两两不同

解题思路

其实就是求恰好有\(\frac{n+k}{2}\)种\(a_i>b_i\)的匹配方案。

先设\(f_{i,j}\)表示到\(a\)的第\(i\)个，已经选择了\(j\)组的方案。转移起来比较麻烦，我们不知道\(b\)中选了哪些。

把\(a\)和\(b\)排序后，设\(l_i\)表示一个最大的数字使得\(a_i>b_{l_i}\)，然后就可以\(dp\)了

之后发现我们很难固定其他配对的大小，可以考虑容斥，设\(g_i\)表示至少有\(i\)对满足\(a_i>b_i\)的方案，那么有\(g_i=f_i\times (n-i)!\)。

然后就可以直接容斥了，因为\(g_i\)中有\(\binom{i}{k}\)中方案选出\(k\)个配对满足，所以容斥系数就是\((-1)^{i-k}\binom{i}{k}\)

答案就是

时间复杂度\(O(n^2)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=2100,P=1e9+9;

ll n,k,C[N][N],a[N],b[N],f[N][N],g[N],l[N],ans;

signed main()

{

    scanf("%lld%lld",&n,&k);

    if((n+k)&1)return puts("0")&0;

    k=(n+k)/2;C[0][0]=1;

    for(ll i=1;i<=n;i++)

        for(ll j=0;j<=i;j++)

            C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;

    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);

    for(ll i=1;i<=n;i++)scanf("%lld",&b[i]);

    sort(a+1,a+1+n);sort(b+1,b+1+n);

    for(ll i=1;i<=n;i++)

        for(ll j=1;j<=n;j++)

            if(b[j]<a[i])l[i]=j;

            else break;

    f[0][0]=1;

    for(ll i=1;i<=n;i++)

        for(ll j=0;j<=n;j++)

            f[i][j]=(f[i-1][j]+(j?f[i-1][j-1]*max(l[i]-j+1,0ll)%P:0))%P;

    for(ll i=n,s=1;i>=0;i--,s=s*(n-i)%P)g[i]=f[n][i]*s%P;

    for(ll i=k;i<=n;i++){

        ll tmp=g[i]*C[i][k]%P;

        (ans+=((i-k)&1)?P-tmp:tmp)%=P;

    }

    printf("%lld\n",ans);

    return 0;

}