【BZOJ 3622】3622: 已经没有什么好害怕的了(DP+容斥原理)

时间：2021-01-15 15:53:57

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

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 683  Solved: 328

Description

【BZOJ 3622】3622: 已经没有什么好害怕的了(DP+容斥原理)

Input

【BZOJ 3622】3622: 已经没有什么好害怕的了(DP+容斥原理)

Output

【BZOJ 3622】3622: 已经没有什么好害怕的了(DP+容斥原理)

Sample Input

4 2
5 35 15 45
40 20 10 30

Sample Output

4

HINT

【BZOJ 3622】3622: 已经没有什么好害怕的了(DP+容斥原理)

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

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

Source

【分析】

　　もう何も怖くない【BZOJ 3622】3622: 已经没有什么好害怕的了(DP+容斥原理)

　　首先n+k为奇特判无解。

　　然后知道要选多少组ai>bj的

　　然后就选吧。

　　先两个都排一遍序

　　$f[i][j]$表示选了a的前$i$组后有$j$组$ai>bj$的，的方案数。

　　这个很简单好吗！！（我昨天晚上看这题时候绝对脑抽）

　　$f[i][j]=f[i-1][j]+f[i-1][j-1]*(mx[i]-j+1)$ 剩下的先不用管，后面乱排乘一个阶乘

　　$mx[i]$表示最多前$mx[i]$个$b$数组小于$a[i]$

　　但是！！不能保证刚好就等于你要的组数，可能大于它。于是容斥大法就来了。

　　$dp[i]=f[n][i]*(n-i)!-dp[j]*C[j][i] (j>i)$

　　组合数也递推就好了。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 2010

 #define Mod 1000000009

 #define LL long long

 LL mymax(LL x,LL y) {return x>y?x:y;}

 LL a[Maxn],b[Maxn],f[Maxn][Maxn],mx[Maxn],dp[Maxn],p[Maxn];

 LL c[Maxn][Maxn];

 int main()

 {

     LL n,k;

     scanf("%lld%lld",&n,&k);

     if((n+k)&) printf("0\n");

     else

     {

         k=(n+k)/;

         for(LL i=;i<=n;i++) scanf("%lld",&a[i]);

         for(LL i=;i<=n;i++) scanf("%lld",&b[i]);

         sort(a+,a++n);

         sort(b+,b++n);

         LL st=;

         for(LL i=;i<=n;i++)

         {

             while(a[i]>b[st+]&&st<n) st++;

             mx[i]=st;

         }

         memset(f,,sizeof(f));

         for(int i=;i<=n;i++) f[i][]=;

         for(LL i=;i<=n;i++)

          for(LL j=;j<=i;j++)

          {

              f[i][j]=(f[i-][j]+f[i-][j-]*mymax(mx[i]-j+,))%Mod;

          }

         for(LL i=;i<=n;i++) c[i][]=;

         for(LL i=;i<=n;i++)

          for(LL j=;j<=i;j++)

          {

              c[i][j]=(c[i-][j]+c[i-][j-])%Mod;

          }

         p[]=;

         for(LL i=;i<=n;i++) p[i]=(p[i-]*i)%Mod;

         for(LL i=n;i>=k;i--)

         {

             dp[i]=(f[n][i]*p[n-i])%Mod;

             for(LL j=i+;j<=n;j++)

             {

                 dp[i]=dp[i]-c[j][i]*dp[j];

                 dp[i]=(dp[i]%Mod+Mod)%Mod;

             }

         }

         printf("%lld\n",dp[k]);

     }

     return ;

 }

もう何も怖くない(呵呵

2017-04-06 14:16:58

相关文章