P10813 【MX-S2-T4】 换 题解

· · 题解

显然，序列 a 是否能通过操作排好序只和每个元素的相对大小有关，因此我们可以先求出将其离散化后的序列 b。对于序列 b，设其值域为 [1,w]，我们考虑序列 b 拆成 w+1 个 01 串 c_0,c_1,\dots,c_w，其中 c_{i,j}=[b_j \ge i]，那么序列 b 能通过操作排好序当且仅当它拆成的 w+1 个 01 串都能通过操作排好序。

我们可以暴力求出每个 01 串是否合法，并把每个序列 b 看成一个 00\cdots0 到 11\cdots1 的长度为 w 的路径，对合法的 01 串做一个 dp 即可得到合法的序列 b 的数量。具体地，设 f_{i,s} 表示，当前是路径上的第 i 个 01 串，其状态表示为 s，此时满足条件的序列 b 的数量。初始化 f_{0,0}，转移方程为：

f_{i,s}= \begin{cases} 0 & h_s=0\\ \sum\limits_{t \subset s} f_{i-1,t} & h_s=1 \end{cases}

其中，h_s=1 表示 s 合法，h_s=0 表示 s 不合法。由于每次转移至少要改变一位，所以转移方程中的 t 不能等于 s。可以使用高维前缀和优化，做到时间复杂度 \mathcal O(n^22^n)。

求出 f_{w,2^n-1} 后，只需要考虑如何把序列 b 转回序列 a 了。此时相当于要在 V 个数中选出 w 个数作为离散化前每个元素的值，方案数为 V \choose w，因此答案等于 \sum\limits_{w=1}^n f_{w,2^n-1} \cdot {V \choose w}，暴力计算即可。

时间复杂度 \mathcal O((n^2+m)2^n)。

const int N=20,M=505,S=1<<18,mod=1e9+7;
int n,k,V,m,p[M],q[M],h[S],sum[S],f[N][S],ans;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int lowbit(int x){
    return x&-x;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void solve(){
    cin>>n>>V>>m;
    for(int i=1;i<=m;i++) cin>>p[i]>>q[i],p[i]--,q[i]--;
    k=1<<n;
    for(int s=0;s<k;s++){
        int t=s;
        for(int i=1;i<=m;i++) if(((t>>p[i])&1)>((t>>q[i])&1)) t=t^(1<<p[i])^(1<<q[i]);
        if(lowbit(t)+t==k) h[s]=1;
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int s=0;s<k;s++) sum[s]=f[i-1][s];
        for(int p=1;p<k;p<<=1){
            for(int s=0;s<k;s++){
                if(s&p) continue;
                add(sum[s|p],sum[s]);
            }
        }
        for(int s=0;s<k;s++){
            if(h[s]==0) f[i][s]=0;
            else f[i][s]=ad(sum[s],mod-f[i-1][s]);
        }
    }
    for(int w=1;w<=n;w++){
        int pro=1;
        for(int i=V-w+1;i<=V;i++) pro=1ll*pro*i%mod;
        for(int i=1;i<=w;i++) pro=1ll*pro*ksm(i,mod-2)%mod;
        add(ans,1ll*pro*f[w][k-1]%mod);
    }
    cout<<ans<<endl;
}