bzoj 3622 已经没有什么好害怕的了 类似容斥，dp
3622: 已经没有什么好害怕的了
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1213 Solved: 576
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
5 35 15 45
40 20 10 30
Sample Output
HINT
输入的2*n个数字保证全不相同。
Source
先把两个数列a，b从小到大排序。
设f[i][j]表示前i对数中，满足糖果大于药片的对数“至少”有j对的方案数。
总共要组n对数，其中糖果大于药片的组数比药片大于糖果的组数多k组，那么总共需要 m=(n+k)/2 对数满足糖果大于药片，剩下的满足药片大于糖果。
先用next[]数组记录对于a中的每个数，在j中有next[i]个数比它小，则a[i]可以和next[i]个数组成糖果大于药片的数对。
进行DP： f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(next[i]-(j-1),0)%mod
这样求出来的是“至少”有j对的方案数，而我们需要的是“恰好”有m对的方案数。
显然（并不）这是一个容斥问题：
f[n][i]表示总共n对数中，至少有i对数满足“糖果大于药片”。在a数列中，剩下的(n-i)个数各自要找b数列中剩下的一个数配对，方案共有 (n-i)! (←阶乘) 种。
设dp[n][i]=“n对数中恰好i对数满足糖果大于药片”的方案数，则dp[n][i] = f[n][i]*(n-i)! -多余部分
接下来分析多余部分：
若j>i,在dp[n][j]中(这里的dp[n][j]是已经算完的正确答案，为此需要倒序计算)的一部分可能会被算进f[n][i]中，这种误算的方案有C[j][i]*dp[n][j]种。
所以： dp[n][i]=f[n][i]*(n-i)! – ( Σ(i<j<=n) C[j][i]*dp[n][j] ) 注意取模
之后发现dp数组只用到了[n][i]，所以第一维可以扔掉了
十分巧妙，倒着去推出，估计看到数据范围我也不会去想这样的方法。
容斥一般20还行，这么多貌似(⊙o⊙)…
1 #pragma GCC optimize(2) 2 #pragma G++ optimize(2) 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<cstdio> 7 #include<cstring> 8 9 #define ll long long 10 #define N 2007 11 #define mod 1000000009 12 using namespace std; 13 inline int read() 14 { 15 int x=0,f=1;char ch=getchar(); 16 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 17 while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} 18 return x*f; 19 } 20 21 int n,m; 22 int a[N],b[N]; 23 int num[N]; 24 ll f[N][N],dp[N],C[N][N],A[N]; 25 26 void init_C() 27 { 28 for (int i=0;i<=n;i++)C[i][0]=1; 29 for (int i=1;i<=n;i++) 30 for (int j=1;j<=i;j++) 31 C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; 32 A[1]=1; 33 for (int i=2;i<=n;i++)(A[i]=A[i-1]*i)%=mod; 34 } 35 int main() 36 { 37 n=read(),m=(read()+n)/2; 38 for (int i=1;i<=n;i++)a[i]=read(); 39 for (int i=1;i<=n;i++)b[i]=read(); 40 sort(a+1,a+n+1),sort(b+1,b+n+1); 41 for (int i=1,j=1;i<=n;i++) 42 { 43 while(j<=n&&b[j]<a[i])j++; 44 num[i]=j-1; 45 } 46 init_C(); 47 for (int i=0;i<=n;i++)f[i][0]=1; 48 for (int i=1;i<=n;i++) 49 for (int j=1;j<=i;j++) 50 f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(num[i]-j+1,0))%mod; 51 for (int i=n;i>=m;i--) 52 { 53 dp[i]=f[n][i]*A[n-i]%mod; 54 for(int j=i+1;j<=n;j++) 55 dp[i]=((dp[i]-dp[j]*C[j][i]%mod)%mod+mod)%mod; 56 } 57 printf("%lld\n",dp[m]); 58 }