【JZOJ4924】【NOIP2017提高组模拟12.17】向再见说再见

题目描述

数据范围

=w=

设h[i]表示，甲队得到i分的方案数。

那么h[(n+k)/2]和h[(n−k)/2]就是答案。

---

设g[i]表示，甲队得到至少i分的方案数。

那么h[i]=g[i]−∑j>ih[j]∗Cij。

思考这条递推式的正确性：

考虑g[i]比h[i]多了什么，对于每个j>i，h[j]中的每个单位表示：

甲队中的j个元素，都与乙队中的j个元素一一对应。

如果从这j个元素中任意选择i个元素，那么有Cij中选法，其中每种选法都可以唯一扩展到这个单位。

---

g可用动态规划求。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

using namespace std;

const char* fin="aP3.in";

const char* fout="aP3.out";

const ll inf=0x7fffffff;

const ll maxn=2007,mo=1000000007;

ll n,m,i,j,k,ans;

ll a[maxn],b[maxn];

ll A[maxn],B[maxn];

ll f[2][maxn];

ll c[maxn][maxn];

ll h[maxn],fact[maxn];

int main(){

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

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

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

    for (i=0;i<=n;i++){

        c[0][i]=1;

        for (j=1;j<=i;j++) c[j][i]=(c[j-1][i-1]+c[j][i-1])%mo;

    }

    if ((n+m)%2) printf("0");

    else{

        ll v=0;

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

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

        j=0;

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

            while (j<n && a[i]>b[j+1]) j++;

            A[i]=j;

        }

        f[v][0]=1;

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

            v^=1;

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

                f[v][j]=0;

                f[v][j]=f[1-v][j];

                if (j) f[v][j]=(f[v][j]+f[1-v][j-1]*(A[i]-(j-1)))%mo;

            }

        }

        fact[0]=1;

        for (i=1;i<=n;i++) fact[i]=fact[i-1]*i%mo;

        for (i=n;i>=0;i--){

            h[i]=f[v][i]*fact[n-i];

            for (j=i+1;j<=n;j++){

                h[i]=((h[i]-c[j-i][j]*h[j])%mo+mo)%mo;

            }

            if (i==(n+m)/2 || i==(n-m)/2) ans=(ans+h[i])%mo;

        }

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

    }

    return 0;

}