题解：P10813 【MX-S2-T4】 换
Lucyna_Kushinada
·
·
题解
2025/11/12 upd：修改笔误。
好题，融入了一些自己的思路历程，可能看得会更舒服一点。
分析题目所给的操作，很难发现什么有用的性质，交换路径与 a 序列密切相关，如果不清楚交换路径，根本无法继续分析 a 单调不降的要求。
然后发现 n\le 18,m\le 500，n 的范围更像是状压的复杂度，允许 O(2^n) 枚举，m 显得有些神秘，但是计算一下 m\times 2^n=131072000，刚好跑得了，猜测是正解复杂度的一部分。
$n\le 18$ 有很强烈的指示性，但现在似乎还没有任何有关 $2^n$ 的东西。
接下来的一步比较有跳跃性，考虑换一种判定一个 $a$ 合法的方式，枚举 $x\in [0,V]$，将 $a_i< x$ 的换成 $0$，反之换为 $1$，如果对于每个 $x$，其生成的 01 序列都合法，那么就合法。
如果想到了这个，那么离做出这题就不远了。
可能的 01 序列一共有 $2^n$ 中，可以预处理 $g_S\in \{0,1\}$，表示 $S$ 是否是合法的 01 序列，时间复杂度 $O(m \times 2^n)$。
继续考虑判定的过程，发现 $x\in [0,V]$ 是有点宽松的，有些 $x$ 的连续段的作用效果本质一样（生成了相同的 01 序列），其实只需要离散一下，用 $x\in a$ 来判定即可。
考虑生成一个合法 $a$ 序列的过程，初始时每个位置都是空的，显然合法，考虑从小到大填数，假设当前填的是 $x$，每次选若干个位置填成 $x$，相应的 01 序列也会发生有规律的变化（那几个位置都变为 $1$），如果生成的过程中所有历经的 01 序列都是合法的，那么就能生成一个合法的 $a$ 序列。
那么就可以考虑设计出一个 dp 转移来计数。
设 $f_{i,S}$ 表示**从大到小**插入了 $i$ 种数（只关心相对大小），当前位置的选定情况（同时也是 01 序列的情况，因为新填入的位置在 01 序列上一定为 $1$）为 $S$ 时的方案数，有转移：
$$\displaystyle f_{i,S}=g_S\times \sum_{T\subset S} f_{i-1,T}$$
这个 dp 转移是离线的，直接跑 $n$ 次高位前缀和就行了，这里使用 fwt 实现。
那么答案就是 $\displaystyle \sum_{i=1}^n \binom{V}{i} f_{i,U}$，其中 $U$ 是全集，代表 $a$ 的所有位置均已填数，生成了完整的 $a$，原 dp 求出的是离散的方案数，还需要结合值域 $V$ 和种类数 $i$，用组合数求出真正的方案数。
时间复杂度 $O(m\times 2^n+n^2\times 2^n+ n\log V)$，跑得还怪快的。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define N 19
#define S (1<<18)+5
#define M 505
#define int long long
const int mod=1e9+7;
int n,v,m,p[M],q[M],a[N],f[N][S];
int g[S],tmp[S],tot;
inline int qpow(int a,int b=mod-2){
int ans=1;
while(b){
if(b&1){
ans=ans*a%mod;
}
a=a*a%mod;
b>>=1;
}
return ans;
}
inline int C(int n,int m){
if(n<m){
return 0;
}
int ans=1,fac=1;
rep(i,1,m){
ans=ans*(n-i+1)%mod;
fac=fac*i%mod;
}
return ans*qpow(fac)%mod;
}
inline void init(){
tot=(1<<n)-1;
rep(s,0,tot){
rep(i,1,n){
a[i]=(s>>(i-1))&1;
}
rep(i,1,m){
if(a[p[i]]>a[q[i]]){
swap(a[p[i]],a[q[i]]);
}
}
g[s]=is_sorted(a+1,a+1+n);
}
}
inline void fwt(int *f,int n){
int len=2,nx=1;
while(len<=n){
int i=0;
while(i<n){
rep(j,0,nx-1){
f[i+j+nx]=(f[i+j+nx]+f[i+j])%mod;
}
i+=len;
}
len<<=1;
nx<<=1;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>v>>m;
rep(i,1,m){
cin>>p[i]>>q[i];
}
init();
f[0][0]=g[0];
rep(i,1,n){
rep(s,0,tot){
tmp[s]=f[i-1][s];
}
fwt(tmp,1<<n);
rep(s,0,tot){
f[i][s]=(tmp[s]-f[i-1][s]+mod)%mod*g[s];
}
}
int ans=0;
rep(i,1,n){
ans=(ans+C(v,i)*f[i][tot]%mod)%mod;
}
cout<<ans;
return 0;
}
```