想一想就是放n^2，先转化一下变成计算至少要(n+k)/2个糖果大于药片

考虑没有重复，先排下序，然后处理出每个a[i]可以和多少b[i]匹配满足条件

本来我的想法就是直接f[i][j]表示枚举到第i位j个满足条件

结果转移不了，改了改变成f[i][j]表示枚举到第i位至少j个满足条件

然后容斥

————————————————————————————————————

upd：之前讲的不知所云。。。

排完序以后处理出d[i]表示第i个糖果可以和1~第d[i]个药片匹配令糖大于药

我们要算的是匹配到第n颗糖，用了n个药片，有k颗糖>它对应的药片，设它为dp[n][n][k]吧

这个东西不好弄，我们容斥曲线救国

设f[i][j]表示匹配到第i颗糖，和j个药片匹配（对应药片可以重复），且糖均大于药的方案数

对于当前f[i][j]，假如我用用过的药，方案数就是f[i-1][j]，假如用一个没用过的，就有d[i]-(j-1)种选择

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

f[n][n]相当于搞出了匹配到第n颗糖，用了n个药片，有n颗糖>它对应的药片，也就是dp[n][n][n]

而其实前面两维是没有用的，只用dp[n]表示匹配到第n颗糖，用了n个药片，至少有n颗糖>它对应的药片即可

那么如何通过dp[n]倒着推出dp[n-1]……dp[k]呢？

假设我们现在要求dp[x]，大于x的已经搞完了

既然需要正确匹配x个，那么f[n][x]是表示匹配到第n颗糖，用了x药片，全部糖大于药的方案数，假如换种想法，匹配了这x个药片以后，剩下的n-x颗糖随便乱匹配，此时正确匹配数应该是>=x的

所以首先先选n-x颗糖一一放去那些没有用于匹配的药片那，方案数为(n-x)!

所以f[n][x]*(n-x)!就是n颗糖一一对应，且至少有x颗糖比它对应的药片大的方案数了

然后需要减掉包含在里面正确匹配数==x+1的，减去正确==x+2的……，这就是容斥的思想，注意不是加减交互，因为我们已经算出的是刚好有x+1颗糖大于药的方案数了。

所以dp[x]=f[n][x]*(n-x)!-sigema(i>x)dp[i]*C(i,x) 组合数的意思是在i组正确匹配中，选出x个对于当前是组成那x个正确匹配的，剩下i-x是后面乱选不小心搞出来的

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           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
           
            =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;}