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);
}