bzoj 3622 已经没有什么好害怕的了

bzoj 3622 已经没有什么好害怕的了

​​ Description

Input

Output

Sample Input 4 2 5 35 15 45 40 20 10 30 Sample Output 4 HINT

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

还有输入应该是第二行是糖果，第三行是药片 要求糖果比药片多的组数多k个那么实际上我们需要n+k>>1这么多组因为首先至少需要一半的组是比他多的然后剩下只需要多k/2组即可满足条件 不能整除显然无解 分别排序从小到大算出les[i]表示第i个位置的糖果比多少药片大 那么设dp[i][j]表示前i个糖果有j个比药片大的方案数 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*max(0,i-(j-1)) 最后方案数应该乘剩下的随便放 但这样显然算的方案是大于等于的 我们设tmp[i]表示恰好i组的数量那么 对于每一个i< j<=n来说 我们都可以有Cij C j i 种选择方式使得tmp[j]出现在dp[n][i]中 减去即可

#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=2e3+10;const int mod=1e9+9;inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}inline int dec(int x,int v){return x-v<0?x-v+mod:x-v;}int c[N][N],n,k,a[N],b[N],les[N],dp[N][N],tmp[N],jc[N];inline void init(){ for (int i=0;i<=2000;++i) c[i][0]=1; for (int i=1;i<=2000;++i) for (int j=1;j<=i;++j) c[i][j]=inc(c[i-1][j],c[i-1][j-1]);}int main(){ freopen("bzoj3622.in","r",stdin); n=read();k=read();init();jc[0]=1;k=k+n>>1; for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;i<=n;++i) b[i]=read(); sort(a+1,a+n+1);sort(b+1,b+n+1);int now=0; for (int i=1;i<=n;++i){ while(b[now]=k;--i){ tmp[i]=(ll)dp[n][i]*jc[n-i]%mod; for (int j=i+1;j<=n;++j) tmp[i]=dec(tmp[i],(ll)tmp[j]*c[j][i]%mod); }printf("%d\n",tmp[k]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。