[JZOJ5429]【NOIP2017提高A組集訓10.27】排列

Description

有兩個長度為n的排列A和B，定義排列的價值f(A,B)為所有滿足A[i]>B[i]的位置i的數量。

現給出n，A，B和S，其中A和B中有一些位置的數未知，問有多少種可能的填數的方案使得f(A,B)=S

對于100%的資料滿足，1<=S<=n<=4000

保證不存在一個位置i滿足A[i]=0且B[i]=0

Solution

直接做很難做，不妨考慮轉化一下

顯然上面為0和下面為0的情況是相似的，可以分開考慮，兩個都不為0的直接判掉。

下面隻讨論上面為0的情況

我們可以把剩下的數拉出來排個序，按順序選。

設 F[i][j] 表示標明了前i個，造成了j的貢獻。

設 r 為第i個比對應的b的多少個大。

轉移似乎很顯然，F[i][j]=F[i−1][j]+F[i][j−1]∗(r−(j−1))

最後 F[m][j]=F[m][j]∗(m−j)!

把這些沒造成貢獻的排列一下。

但是，這樣是錯的。

有可能對于某個點沒有造成貢獻的，選了後面的b，令後面的即使不得不選前面的而造成了額外的貢獻。

是以我們改一下狀态

設 F[i][j] 表示標明了前i個，至少造成了j的貢獻。

這樣上面的轉移成立。

現在要求剛好為j的答案，可以容斥一下。

可以發現 F[m][k],k>j 在 F[m][j] 中多算了 Cjk 次。

容斥一下即可。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cstdlib>
#include <set>
#include <map>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mo 1000000007
#define N 4005
#define LL long long
using namespace std;
int n,m,a[N],b[N],d[N],s[N];
LL f[N][N],g[N],h[N],js[N],ny[N];
bool bz[N];
LL ksm(LL k,LL n)
{
    LL s=;
    for(;n;n>>=,(k*=k)%=mo) if(n&) (s*=k)%=mo;
    return s;
}
LL zh(LL m,LL n)
{
    return js[n]*ny[m]%mo*ny[n-m]%mo;
}
int main()
{
    cin>>n>>m;
    fo(i,,n) scanf("%d",&a[i]);
    fo(i,,n) scanf("%d",&b[i]);
    js[]=ny[]=;
    fo(i,,n) js[i]=js[i-]*(LL)i%mo,ny[i]=ksm(js[i],mo-);
    fo(i,,n)
    {
        if(a[i]>b[i]&&b[i]!=) m--;
        if(a[i]==) s[b[i]]++;
        if(a[i]!=) bz[a[i]]=;
    }
    fo(i,,n) 
    {
        if(!bz[i]) d[++d[]]=i;
        s[i]+=s[i-];
    }
    f[][]=;
    fo(i,,d[])
    {
        fo(j,,s[d[i]-])
        {
            f[i][j]=f[i-][j];
            if(j) (f[i][j]+=f[i-][j-]*(LL)(s[d[i]-]-j+)%mo)%=mo;
            if(i==d[]) (f[i][j]*=js[d[]-j])%=mo;
        }
    }
    fo(j,,s[d[d[]]-])
    {
        g[j]=f[d[]][j];
        LL v=-;
        fo(k,j+,s[d[d[]]-])
        {
            (g[j]+=v*zh(j,k)*f[d[]][k]%mo)%=mo;
            v=-v;
        }   
    }
    d[]=;
    memset(s,,sizeof(s));
    memset(f,,sizeof(f));
    memset(bz,,sizeof(bz));
    fo(i,,n)
    {
        if(b[i]==) s[a[i]]++;
        else bz[b[i]]=;
    }
    fod(i,n,)  
    {
        if(!bz[i]) d[++d[]]=i;
        s[i]+=s[i+];
    }
    f[][]=;
    fo(i,,d[])
    {
        fo(j,,s[d[i]+])
        {
            f[i][j]=f[i-][j];
            if(j) (f[i][j]+=f[i-][j-]*(s[d[i]+]-j+)%mo)%=mo;
            if(i==d[]) (f[i][j]*=js[d[]-j])%=mo;
        }
    }
    fo(j,,s[d[d[]]+])
    {
        h[j]=f[d[]][j];
        LL v=-;
        fo(k,j+,s[d[d[]]+])
        {
            (h[j]+=v*zh(j,k)*f[d[]][k]%mo)%=mo;
            v=-v;
        }   
    }
    LL ans=;
    fo(j,,m) (ans+=g[j]*h[m-j]%mo)%=mo;
    printf("%lld\n",(ans+mo)%mo);
}