首页 > 代码库 > BZOJ 3622(已经没有什么好害怕的了-Dp+容斥原理)
BZOJ 3622(已经没有什么好害怕的了-Dp+容斥原理)
3622: 已经没有什么好害怕的了
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 7 Solved: 6
[Submit][Status]
Description
Input
Output
Sample Input
4 2
5 35 15 45
40 20 10 30
5 35 15 45
40 20 10 30
Sample Output
4
HINT
Source
2014湖北省队互测week2
PS:本题的数据中能量互不相同。
1.我们计算出糖果>药片的组数=k
2.我们计算出f[i][j],表示到第i个糖果,糖果>药片的组数为j,且剩下无规定的情况数
(eg:a1>b1,a3>b3,a2不明;
a1>b1,a2>b2,a3不明)
△:此时有重合的情况(如上例),故接下来用容斥。
3.我们计算出f‘[i][j],表示到第i个糖果,糖果>药片的组数为j,且剩下的为糖果<药片的情况数。
显然有
其中(n-i)!表示剩下的全排列方案数
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForDk(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000009) #define MAXN (2000+10) #define MAXK (2000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int n,k; ll f[MAXN][MAXK]={0},C[MAXN][MAXN],jc[MAXN]; int a[2][MAXN]={0},l[MAXN]; //第i组第j个 int main() { // freopen("bzoj3622.in","r",stdin); scanf("%d%d",&n,&k); Rep(i,2) For(j,n) scanf("%d",&a[i][j]); sort((int*)a+1,(int*)a+1+n); sort((int*)a[1]+1,(int*)a[1]+1+n); if ((n+k)&1) {printf("0\n");return 0;} else k=(n+k)/2; /* Rep(i,2) { For(j,n) { printf("%d ",a[i][j]); } cout<<endl; } */ C[0][0]=1; For(i,n) { C[i][0]=C[i][i]=1; For(j,i-1) C[i][j]=add(C[i-1][j],C[i-1][j-1]); } /* Rep(i,n+1) { Rep(j,i+1) cout<<C[i][j]<<' '; cout<<endl; } */ // cout<<k<<endl; int p=0; For(i,n) { while (p<n&&a[1][p+1]<a[0][i]) p++; l[i]=p; } // For(i,n) cout<<l[i]<<' ';cout<<endl; f[0][0]=1; For(i,n) Rep(j,/*min(i,k)+1*/i+1) { f[i][j]=f[i-1][j]; if (j>0&&l[i]-(j-1)>0) f[i][j]=add(f[i][j],mul(f[i-1][j-1],l[i]-(j-1))); } jc[0]=1;For(i,n) jc[i]=mul(jc[i-1],i); // For(i,n) cout<<jc[i]<<' ';cout<<endl; ForDk(i,k/*1*/,n) { f[n][i]=mul(f[n][i],jc[n-i]); Fork(j,i+1,n) f[n][i]=sub(f[n][i],mul(f[n][j],C[j][i])); } /* For(i,n) { Rep(j,min(i,k)+1) cout<<f[i][j]<<' '; cout<<endl; } */ cout<<f[n][k]<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。