[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);
}