首页 > 代码库 > [BZOJ 3622]已经没有什么好害怕的了（Dp+容斥原理）
[BZOJ 3622]已经没有什么好害怕的了（Dp+容斥原理）
Description
图片略
Solution
对啊，已经没有什么好害怕的了
没有头的麻美学姐还是很萌的（雾
排序预处理p[i]为b中小于a[i]的最大的数的标号
f[i][j]表示前i个糖果使得糖果大于药片的至少有j组
则f[i][j]=f[i-1][j]+f[i-1][j-1]*(p[i]-j+1)
容斥得g[j]=f[n][j]*(n-j)!-∑g[k]*C(j,k) (j+1<=k<=n)
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define MAXN 2002#define Mod 1000000009typedef long long LL;using namespace std;int n,k,a[MAXN],b[MAXN],p[MAXN];LL f[MAXN][MAXN],c[MAXN][MAXN],g[MAXN];int read(){ int x=0,f=1;char c=getchar(); 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 main(){ n=read(),k=read(); if((n+k)%2) {printf("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); int t=1; for(int i=1;i<=n;i++) { while(a[i]>b[t]&&t<=n)t++; p[i]=t-1; } f[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=i;j++) { if(j)f[i][j]=(f[i-1][j-1]*max(0,p[i]-j+1))%Mod; f[i][j]=(f[i][j]+f[i-1][j])%Mod; } c[1][0]=1;c[1][1]=1; for(int i=2;i<=n;i++) for(int j=0;j<=i;j++) {if(!j)c[i][j]=1;c[i][j]=(c[i-1][j-1]+c[i-1][j])%Mod;} for(int i=n;i>=k;i--) { g[i]=f[n][i]; for(int j=1;j<=n-i;j++) g[i]=(g[i]*j)%Mod; for(int j=i+1;j<=n;j++) { g[i]=(g[i]-(g[j]*c[j][i])%Mod+Mod)%Mod; } } printf("%d",g[k]); return 0;}
[BZOJ 3622]已经没有什么好害怕的了（Dp+容斥原理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。