BZOJ 3622: 已经没有什么好害怕的了 [容斥原理 DP]

时间：2022-07-19 15:55:50

3622: 已经没有什么好害怕的了

题意：和我签订契约，成为魔法少女吧

真·题意：零食魔女夏洛特的结界里有糖果a和药片b各n个，两两配对，a>b的配对比b>a的配对多k个学姐就可能获胜，求方案数

PS：洛谷月赛拿到了一个Modoka的挂件O(∩_∩)O哈哈~



总的方案数就是\(n!\)，相当于一个做全排列

恰好多k个，那么就是a>b的有\(k=k+\frac{n-k}{2}\)个

恰好\(\rightarrow\)容斥

\[=\ \ge k个的配对方案数\ -\ \ge k+1个\ +\ \ge k+2个\ ...
\]

\(\ge i\)个就是先选出i对a>b的，剩下的任意排列

用个dp吧，先排序，求出\(g[i]\)表示\(a_i\)比\(g[i]\)个b大

\(f[i][j]\)表示前i个a选出j对a>b的方案数

\[ans= \sum_{i=k}^n (-1)^{i-k}f[n][i](n-i)!
\]


然后就一直WA...
原因是，你忘了spring吗，原因相同，我们算方案的时候重复了，每个k+i个配对的方案被考虑了 $\binom{k+i}{k}$ 次呀，应该只被考虑一次才对

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N=2005, P=1e9+9;

inline int read(){

	char c=getchar();int x=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

int n, k, a[N], b[N];

ll f[N][N], fac[N], inv[N], facInv[N]; int g[N];

inline ll C(int n, int m) {return fac[n]*facInv[m]%P*facInv[n-m]%P;}

void dp() {

	int now=0;

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

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

		g[i] = now;

	}

	for(int i=0; i<=n; i++) f[i][0]=1;

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

		for(int j=1; j<=g[i]; j++) f[i][j] = (f[i-1][j] + f[i-1][j-1]*(g[i]-j+1)%P )%P;// printf("f %d %d  %lld\n",i,j,f[i][j]);

}

int main() {

	freopen("in","r",stdin);

	n=read(); k=read(); if((n+k)&1) {puts("0"); return 0;}

	k += (n-k)/2;

	for(int i=1; i<=n; i++) a[i]=read();

	for(int i=1; i<=n; i++) b[i]=read();

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

	inv[1]=1; fac[0]=facInv[0]=1;

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

		if(i!=1) inv[i] = (P-P/i)*inv[P%i]%P;

		fac[i] = fac[i-1]*i%P;

		facInv[i] = facInv[i-1]*inv[i]%P;

	}

	dp();

	ll ans=0;

	for(int i=k; i<=n; i++) ( ans += ( ((i-k)&1) ? -1 : 1 ) * fac[n-i] * f[n][i]%P * C(i, k)%P )%=P;

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

}

相关文章