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

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 1033  Solved: 480

[ ][ ][ ]

Description

Input

Output

Sample Input

4 2

5 35 15 45

40 20 10 30

Sample Output

4

HINT

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

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

 

 

考虑dp

两个数组排序,可以求出有m组糖>药

f[i][j]表示前i个糖  至少j组 糖>药

转移还是比较简单

f[i][j]=f[i-1][j]+f[i-1][j-1]*(p[i]-j+1,0);

p[]表示排序后最多对于i糖最多选到j药，使其满足糖>药

现在需要对f数组进行处理,让其变成恰好j组糖>药

dp[i]表示所有糖,有恰好i组糖>药

dp[i]=f[n][i]*(n-i)!-sum((i<j<=n)C[j][i]*dp[j])

(n-i)!表示剩下的糖药任意配对

C[j][i]*dp[j]表示在j组糖>药中选择i组

答案就是dp[m]

(模数取错调了很久,习惯性的以为1e9+7了woc)

我也不知道这个去除冗余的方法算不算容斥，但网上都说是就算它是吧233

 

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long long#define N 2005#define mod 1000000009using namespace std;int p[N],a[N],b[N],n,m;ll f[N][N],fac[N],dp[N],c[N][N];void pre(){    for(int i=0;i<=2000;i++)c[i][i]=c[i][0]=1;    for(int i=1;i<=2000;i++)    for(int j=1;j
         
          =m;i--){        dp[i]=(fac[n-i]*f[n][i])%mod;        for(int j=i+1;j<=n;j++)        dp[i]=(dp[i]-dp[j]*c[j][i])%mod;    }    dp[m]<0?dp[m]+=mod:1;    cout<