题解 P4859 【已经没有什么好害怕的了】

这里提供一种不需要二项式反演的做法。

solution:

令 dp[i][j] 为前i个排好序的糖果和药片中，有且仅有j个糖果大于药片的方案数。

考虑如何匹配新加进来的糖果和药片：

situation 1:

若 a[i]>b[i]，我们找到最大的t使得 a[t]<b[i]。

那么我们可以使大于b[i]的i-k个糖果与b[i]匹配。

同时，因为b数组是递增的，a[i]>b[i] 意味着a[i]> \forall b[j],(j<i)。

因此也可以让a[i]去取代 i-j 个小于匹配药片的糖果。

这一部分的方案数为：

(2*i-j-k)*dp[i-1][j-1]

同时也可以让a[i]去取代那些大于本来匹配的药片，但小于b[i]的糖果，这一部分的方案数为：

(j-(i-1-t))*dp[i-1][j]

因此，对于 a[i]>b[i] 的情况，我们有:

dp[i][j]=(2*i-j-k)*dp[i-1][j-1]+(j-(i-1-t))*dp[i-1][j]

situation 2:

若 a[i]<b[i]，我们找到最大的t使得 a[i]>b[t]。

我们可以让a[i]去取代那些匹配的药片大于它自己，但不大于a[i]的糖果，这部分的方案数为：

(t-(j-1))*dp[i-1][j-1]

我们还可以让a[i]去匹配一个比它大的药片方案数为：

(i-k)*dp[i-1][j]

因为糖果被排好序了，因此 b[i]>a[i]>\forall a[j],(j<i) 。

因此，我们还可以让a[i]去随便替换一个之前匹配的药片不大与自己的糖果，方案数为：

j*dp[i-1][j]

因此，对于 a[i]<b[i] 的情况，我们有：

dp[i][j]=(t-(j-1))*dp[i-1][j-1]+(i-k+j)*dp[i-1][j]

递推即可：

code:

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[2005],b[2005];
long long dp[2005][2005];
const long long md=1e9+9;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        if(a[i]>b[i]){
            int t=i;
            while(t&&a[t]>b[i])t--;
            for(int j=0;j<=i;j++){
                if(j)dp[i][j]=(2*i-t-j)*dp[i-1][j-1]%md;
                dp[i][j]=(dp[i][j]+(j-i+t+1)*dp[i-1][j])%md;
            }
        }else {
            int t=i;
            while(t&&b[t]>a[i])t--;
            for(int j=0;j<=i;j++){
                if(j)dp[i][j]=(t-j+1)*dp[i-1][j-1]%md;
                dp[i][j]=(dp[i][j]+(i-t+j)*dp[i-1][j])%md;
            }
        }
    }
    printf("%lld\n",dp[n][(n+k)>>1]);

    return 0;
}