想一想就是放n^2
考虑没有重复,先排下序,然后处理出每个a[i]可以和多少b[i]匹配满足条件
本来我的想法就是直接f[i][j]表示枚举到第i位j个满足条件
结果转移不了,改了改变成f[i][j]表示枚举到第i位至少j个满足条件
然后容斥
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const LL mod=1e9+9; LL a[2100],b[2100];int d[2100]; LL f[2100][2100],dp[2100]; LL fac[2100],c[2100][2100]; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,k; scanf("%d%d",&n,&k);k=(n+k)/2; for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=1;i<=n;i++)scanf("%lld",&b[i]); sort(a+1,a+n+1);sort(b+1,b+n+1); int it=0; for(int i=1;i<=n;i++) { while(a[i]>b[it+1]&&it<n)it++; d[i]=it; } memset(f,0,sizeof(f)); for(int i=0;i<=n;i++)f[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) f[i][j]=(f[i-1][j]+(f[i-1][j-1]*max(d[i]-(j-1),0))%mod)%mod; fac[0]=1;for(int i=1;i<=n;i++)fac[i]=(fac[i-1]*i)%mod; 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; memset(dp,0,sizeof(dp)); for(int i=n;i>=k;i--) { dp[i]=(f[n][i]*fac[n-i])%mod; for(int j=n;j>i;j--) dp[i]=((dp[i]-dp[j]*c[j][i])%mod+mod)%mod; } printf("%lld\n",dp[k]); return 0; }