bzoj3622已经没有什么好害怕的了

题意：

给n个数Ai，n个数Bi，将Ai中的数与Bi中的数配对，求配对Ai比Bi大的比Bi比Ai大的恰好有k组的方案数。n，k≤2000

题解：

蒟蒻太弱了只能引用神犇题解

“

我们将两个读入的数组排序,令 next[i] 表示最大的 j 满足 A[i]>B[j],令f[i][j]表示枚举到第i个A时，有j组A>B，但剩下的情况是不考虑的，则f[i][j]=f[i-1][j]+f[i-1][j-1]*(next[i]-j+1)。但若把 f[n][s] 直接输出会WA因为会有这种情况出现:

a1，a2，a3

b1，b2，b3

a1>b1 a2>b2 a3>b3

那么((a1，b1)，(a2，b2)，a3不明)和((a1，b1)，(a3，b3)，a2不明)就会被视为两种答案，可见我们要求出的是 f’[n][s] 表示n个A，有s组A>B，剩下的都是B>A

这里就要用容斥了

f'[n][i]=f[n][i]*(n-i)!-sigma(j,i+1,n)f'[n][j]*C[j][i]

(n-i)!是枚举后面 n-i 可能的方案，f‘[n][j]*C(j, i) 表示 f[n][i] 中实际有 j 组B>A却被计入f[n][i]的数量

f'[n][s]就是答案了，总时间复杂度为 O(n²)

”

C(j,i)要递推，不然要溢出。

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define dec(i,j,k) for(int i=j;i>=k;i--)

 #define maxn 2100

 #define mod 1000000009

 #define ll long long

 using namespace std;

 int s[maxn],p[maxn],next[maxn],n,k; ll f1[maxn][maxn],f2[maxn],C[maxn][maxn],P[maxn];

 inline int read(){

     char ch=getchar(); int f=,x=;

     while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();} while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 int main(){

     n=read(); k=read(); if((n-k)&){printf(""); return ;} k=((n-k)>>)+k;

     inc(i,,n)s[i]=read(); inc(i,,n)p[i]=read(); sort(s+,s+n+); sort(p+,p+n+);

     int l=; inc(i,,n){while(p[l]<s[i]&&l<=n)l++; next[i]=l-;}

     f1[][]=; inc(i,,n){f1[i][]=; inc(j,,n)f1[i][j]=(f1[i-][j]+f1[i-][j-]*(ll)max(next[i]-j+,)%mod)%mod;}

     P[]=; inc(i,,n)P[i]=P[i-]*(ll)i%mod;

     inc(i,,n){C[i][]=; inc(j,,i)C[i][j]=(C[i-][j]+C[i-][j-])%mod;}

     dec(i,n,k){

         f2[i]=; inc(j,i+,n)f2[i]=(f2[i]+f2[j]*C[j][i]%mod)%mod;

         f2[i]=f1[n][i]*P[n-i]%mod-f2[i]; if(f2[i]<)f2[i]+=mod;

     }

     printf("%lld",f2[k]); return ;

 }

20160610

巴特西

bzoj3622已经没有什么好害怕的了

最新文章

热门文章