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

本文主要是介绍[bzoj3622][DP][容斥原理]已经没有什么好害怕的了，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

4 2

5 35 15 45

40 20 10 30

Sample Output

4

HINT

输入的2*n个数字保证全不相同。

还有输入应该是第二行是糖果，第三行是药片

题解

DP呀..
从小到大排序
显然我们要找 $\frac{n+k}{2}$ 个糖果比药片大的组合
朴素dp方程，设 $f[i][j]$ 表示前 $i$ 个中找到 $j$ 个合法组合其它不管的数量
转移有

$f [i] [j] = f [i - 1] [j] + f [i - 1] [j - 1] * (p o s [i] - j + 1)$ $f[i][j]=f[i-1][j]+f[i-1][j-1]*(pos[i]-j+1)$
其中 $pos[i]$ 表示 $i$ 最多能取到哪一位
会有重复
因为
a1>b1 a2>b2 a3>b3
选(a1,b1,a2,b2)和(a1,b1,a3,b3)会被判为两种不同情况
于是设 $g[i]$ 表示 $n$ 个钟只有 $i$ 个合法情况的状态数
转移有
$g [i] = f [n] [i] * (n - i)! - \sum j = i + 1 n g [j]$ $g[i]=f[n][i]*(n-i)!-\sum_{j=i+1}^{n}g[j]$
前面表示只取i个，后面任选
然后去掉比i多的数目的算到i里的东西
就可以了。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define mod 1000000009
#define LL long long
using namespace std;
LL pow_mod(LL a,LL b)
{LL ret=1;while(b){if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret;
}
LL inv[2005],pre[2005];
LL C(int n,int m){return pre[n]*inv[m]%mod*inv[n-m]%mod;}
int a[2005],b[2005],n,m,pos[2005];
LL f[2005][2005],g[2005];
void dl(LL &x,LL y){x-=y;if(x<0)x+=mod;}
int main()
{pre[0]=1;for(int i=1;i<=2000;i++)pre[i]=pre[i-1]*i%mod;inv[2000]=pow_mod(pre[2000],mod-2);for(int i=1999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;scanf("%d%d",&n,&m);if((n+m)%2){puts("0");return 0;}m=(n+m)/2;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+1+n);sort(b+1,b+1+n);int pa=0;for(int i=1;i<=n;i++){while(b[pa+1]<a[i]&&pa<n)pa++;pos[i]=pa;}f[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++){if(j!=0)f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(0,pos[i]-j+1))%mod;else f[i][j]=f[i-1][j];}for(int i=n;i>=m;i--){g[i]=f[n][i]*pre[n-i]%mod;for(int j=i+1;j<=n;j++)dl(g[i],g[j]*C(j,i)%mod);}printf("%lld\n",g[m]);return 0;
}