ARC160F 题解

First Post:

Last Update:

这道题加深了我对排列转化为 01 序列这个技巧的理解。

首先考虑怎么解决单次询问。排列的大小关系不好考虑，但如果我们考虑每个值 ，将 的值标为 ， 的值标为 ，那么一个排列将对应一个 个 01 序列构成的组。或者说，对应了在 维空间中，一条从 走到 的路径。那么一个合法的排列，其对应的路径中的每个 01 序列必须是能被当前拥有的操作排好序的，因此，我们只需对于每个 01 序列算出其经过当前拥有的操作后是否排好序，然后进行状压 DP 即可。这一部分复杂度为单次 。

但因为有 询问，这个复杂度难以承受，考虑减小询问次数。

定义 “有用操作”为，存在一个排列，在进行了这个操作前的所有操作后，仍然能被这个操作改变状态。

考虑一个有用操作 和其对应的一个 的排列 ，以及一个位置 满足 。在进行一次 后， 这个操作本身会变得无用，但仍然可以使一些操作从无用变为有用，或从有用变为无用。假设操作完之后 从无用变得有用了，那么这说明一开始有 ，交换之后， ，此时 又从有用变得无用了。此时，我们发现无用操作数量增大了 。对于 和 的情况，也是类似的，所以我们可以说明，进行一次有用操作后，无用操作数量会增大至少 。

也就是说，整个过程中，其实只有 个操作是有效的。我们处理数组 表示当前操作 是否有效。在进行了一次有效操作后，我们发现只有 形式的操作的有效性会受影响，此时我们枚举所有 01 序列，暴力更新这些操作的可行性即可。这单次也是 的。

所以总复杂度为 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
const int N = 20,Sz = 1 << 15;
typedef long long ll;
int n,m;
bool eff[N][N];
int bec[Sz]; // 一个 01 序列会被交换成什么样子
bool sorted[Sz];
ll dp[Sz];

int Get(int S,int x) { return S >> x & 1;}
inline ll DP() {
	memset(dp,0,sizeof dp);
	int all = (1 << n) - 1;
	dp[all] = 1; // 在 i = 1 时序列全是 1，满足条件
	for(int S = all - 1;S >= 0;S--) {
		if(!sorted[bec[S]]) continue;
		for(int j = 0;j < n;j++)
			if(!Get(S,j))
				dp[S] += dp[S | (1 << j)];
	}
	return dp[0];
}
int main() {
	cin >> n >> m;
	for(int i = 0;i < n;i++)
		for(int j = i + 1;j < n;j++)
			eff[i][j] = 1;
	for(int i = 0;i <= n;i++)
		sorted[((1 << i) - 1) << (n - i)] = true;
	for(int i = 0;i < (1 << n);i++)
		bec[i] = i;
	ll lastans = 1;
	for(int _ = 1;_ <= m;_++) {
		int a,b,c,d;
		cin >> c >> d;
		c = (c + lastans) % n;
		d = (d + lastans + lastans) % n;
		a = min(c,d);b = max(c,d);
		if(eff[a][b]) {
			for(int i = 0;i < a;i++) eff[i][a] = 0;
			for(int i = a + 1;i < n;i++) eff[a][i] = 0;
			for(int i = 0;i < b;i++) eff[i][b] = 0;
			for(int i = b + 1;i < n;i++) eff[b][i] = 0;
			for(int i = 0;i < (1 << n);i++) {
				if(Get(bec[i],a) > Get(bec[i],b))
					bec[i] ^= (1 << a) ^ (1 << b);
				for(int j = 0;j < a;j++) eff[j][a] |= Get(bec[i],j) > Get(bec[i],a);
				for(int j = a + 1;j < n;j++) eff[a][j] |= Get(bec[i],a) > Get(bec[i],j);
				for(int j = 0;j < b;j++) eff[j][b] |= Get(bec[i],j) > Get(bec[i],b);
				for(int j = b + 1;j < n;j++) eff[b][j] |= Get(bec[i],b) > Get(bec[i],j);
			}
			lastans = DP();
			printf("%lld\n",lastans);
		} else printf("%lld\n",lastans);
	}
	return 0;
}
≡