专栏文章

ARC160F Count Sorted Arrays 题解

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minn1wct
此快照首次捕获于
2025/12/02 05:05
3 个月前
此快照最后确认于
2025/12/02 05:05
3 个月前
查看原文
考虑把排列 pp 拆成 n+1n+1 个 0101 串 c0,c2,…,cnc_0,c_2,\dots,c_n，其中 ci,j=[pj≥i]c_{i,j}=[p_j\ge i]，那么排列 pp 能通过操作排好序当且仅当它拆成的 n+1n+1 个 0101 串都能通过操作排好序。
可以时刻维护每个 0101 串是否合法，把每个排列 pp 看成一个 00⋯000\cdots0 到 11⋯111\cdots1 的长度为 nn 的路径，对合法的 0101 串做一个 dp 即可得到合法的排列 pp 的数量，时间复杂度 O(nm2n)\mathcal O(nm2^n)。
感性理解，其实只有 O(n2)\mathcal O(n^2) 个操作是有效的，而其他操作都不会影响 0101 串的合法性。于是可以时刻维护 fi,jf_{i,j} 表示是否存在 0101 串 cc 满足 cmin⁡(i,j)>cmax⁡(i,j)c_{\min(i,j)} \gt c_{\max(i,j)}，只有当询问的 fai,bif_{a_i,b_i} 为真时才重新 dp 并更新所有的 fai,jf_{a_i,j} 和 fbi,jf_{b_i,j}，否则直接输出上一次询问的结果即可。
时间复杂度 O(n32n)\mathcal O(n^32^n)。
C
const int N=15,W=1<<15;
int n,m,V,f[N][N],g[W],h[W];
ll dp[W],ans=1;
bool get(int s,int x,int y){
	return ((s>>x)&1)>((s>>y)&1);
}
void solve(){
	cin>>n>>m,V=1<<n;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) f[i][j]=1;
	for(int s=0;s<V;s++) g[s]=s;
	for(int i=0;i<=n;i++) h[((1<<i)-1)<<(n-i)]=1;
	for(int c=1;c<=m;c++){
		int x,y;
		cin>>x>>y;
		x=(x+ans)%n,y=(y+ans+ans)%n;
		if(x>y) swap(x,y);
		if(!f[x][y]){
			cout<<ans<<endl;
			continue;
		}
		for(int i=0;i<n;i++) f[x][i]=f[i][x]=f[y][i]=f[i][y]=0;
		for(int s=0;s<V;s++){
			if(get(g[s],x,y)) g[s]^=(1<<x)^(1<<y);
			for(int i=0;i<n;i++){
				if(get(g[s],min(i,x),max(i,x))) f[x][i]=f[i][x]=1;
				if(get(g[s],min(i,y),max(i,y))) f[y][i]=f[i][y]=1;
			}
		}
		for(int s=0;s<V;s++) dp[s]=0;
		dp[0]=1;
		for(int s=1;s<V;s++){
			if(!h[g[s]]) continue;
			for(int i=0;i<n;i++) if(s&(1<<i)) dp[s]+=dp[s^(1<<i)];
		}
		ans=dp[V-1];
		cout<<ans<<endl;
	}
}

评论

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

正在加载评论...