专栏文章

P10813 【MX-S2-T4】 换 题解

CCoffee_zzz/xin
P10813题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimx4p2m
此快照首次捕获于
2025/12/01 16:59
3 个月前
此快照最后确认于
2025/12/01 16:59
3 个月前
查看原文
显然，序列 aa 是否能通过操作排好序只和每个元素的相对大小有关，因此我们可以先求出将其离散化后的序列 bb。对于序列 bb，设其值域为 [1,w][1,w]，我们考虑序列 bb 拆成 w+1w+1 个 0101 串 c0,c1,…,cwc_0,c_1,\dots,c_w，其中 ci,j=[bj≥i]c_{i,j}=[b_j \ge i]，那么序列 bb 能通过操作排好序当且仅当它拆成的 w+1w+1 个 0101 串都能通过操作排好序。
我们可以暴力求出每个 0101 串是否合法，并把每个序列 bb 看成一个 00⋯000\cdots0 到 11⋯111\cdots1 的长度为 ww 的路径，对合法的 0101 串做一个 dp 即可得到合法的序列 bb 的数量。具体地，设 fi,sf_{i,s} 表示，当前是路径上的第 ii 个 0101 串，其状态表示为 ss，此时满足条件的序列 bb 的数量。初始化 f0,0f_{0,0}，转移方程为：
fi,s={0hs=0∑t⊂sfi−1,ths=1f_{i,s}= \begin{cases} 0 & h_s=0\\ \sum\limits_{t \subset s} f_{i-1,t} & h_s=1 \end{cases}
其中，hs=1h_s=1 表示 ss 合法，hs=0h_s=0 表示 ss 不合法。由于每次转移至少要改变一位，所以转移方程中的 tt 不能等于 ss。可以使用高维前缀和优化，做到时间复杂度 O(n22n)\mathcal O(n^22^n)。
求出 fw,2n−1f_{w,2^n-1} 后，只需要考虑如何把序列 bb 转回序列 aa 了。此时相当于要在 VV 个数中选出 ww 个数作为离散化前每个元素的值，方案数为 (Vw)V \choose w，因此答案等于 ∑w=1nfw,2n−1⋅(Vw)\sum\limits_{w=1}^n f_{w,2^n-1} \cdot {V \choose w}，暴力计算即可。
时间复杂度 O((n2+m)2n)\mathcal O((n^2+m)2^n)。
C
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...