自动搬运

查看原文

来自洛谷，原作者为

	p_b_p_b *const int brain=NULL;

搬运于2025-08-24 22:04:38，当前版本为作者最后更新于2019-02-07 10:23:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$$\large \color{purple} My; Blog$$

思路

大佬都说这是套路题……嘤嘤嘤我又被吊打了$Q\omega Q$

显然，这题是要$DP$的。

首先思考一下性质：

为了方便，下面令$k=\frac{n+k}{2}$，即有恰好$k$组糖果比药片大。

显然，$a,b$数组都要先从小到大排序。（$a$是糖果，$b$是药片）

考虑$a_i$造成的影响：

1、若它匹配了一个比它小的$b$，则对于$a_j,j>i$，它匹配比它小的$b$的方案数少了$1$。

2、若它匹配了一个比它大的$b$……似乎又要分类讨论，状态很难记录。

所以，我们$DP$时先考虑第一种的$a_i$，第二种的最后统一分配。

设$dp_{i,j}$表示前$i$个$a$，有$j$个第一种，方案数。

容易得到

其中$r_i$表示$b$中比$a_i$小的个数。

接下来，记$f_i=(n-i)!dp_{n,i}$，也就是把$n-i$个没有匹配的任意分配，得到至少$i$个的答案$f_i$。

那么恰好$i$个的答案呢？

从大往小递推，有

或者用另一种容斥，有

复杂度$O(n^2)$。

代码

#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define sz 2020
	typedef long long ll;
	const ll mod=1e9+9;
	template<typename T>
	inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();
		double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.')
		{
			ch=getchar();
			while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
		}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>
	inline void read(T& t,Args&... args){read(t); read(args...);}
	void file()
	{
		#ifndef ONLINE_JUDGE
		freopen("a.txt","r",stdin);
		#endif
	}
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

ll ksm(ll x,int y)
{
	ll ret=1;
	for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;
	return ret;
}
ll inv(ll x){return ksm(x,mod-2);}

ll fac[sz],_fac[sz];
void init(){fac[0]=_fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

int n,K;
int a[sz],b[sz],r[sz];
ll dp[sz][sz],f[sz];
ll ans[sz];

int main()
{
	file();
	init();
	read(n,K);
	if ((n+K)&1) return puts("0"),0;
	K=(n+K)>>1;
	rep(i,1,n) read(a[i]);
	rep(i,1,n) read(b[i]);
	sort(a+1,a+n+1);sort(b+1,b+n+1);
	int c=0;
	rep(i,1,n)
	{
		while (c<n&&b[c+1]<a[i]) ++c;
		r[i]=c;
	}
	dp[0][0]=1;
	rep(i,1,n)
		rep(j,0,i)
			dp[i][j]=(dp[i-1][j]+(j?1ll*(r[i]-j+1)*dp[i-1][j-1]%mod:0ll))%mod;
	rep(i,0,n) f[i]=dp[n][i]*fac[n-i]%mod;
	drep(i,n,K)
	{
		ans[i]=f[i];
		rep(j,i+1,n) ans[i]=(ans[i]-ans[j]*C(j,i)%mod+mod)%mod;
	}
	cout<<ans[K];
	return 0;
}