P2203题解

题意

给定一个环形 01 序列，每次变化时，对于每个位置，如果前一个值是 1 ，则当前值翻转。求变化 B 次后的序列。

思路

由于 B 的值很大，所以如果对每一次变化进行模拟，效率非常低下。

不难发现，每一次变化后的状态完全是由当前状态决定的，而 N 的范围很小，所以可能的状态总数 2^N 也不是很大，在模拟状态变化的过程中，必然会形成环，环的部分是不必重复模拟的，而是可以通过取模将绕圈的操作都去掉，最终将模拟的次数控制在状态数量之内。

模拟的时候可以用位运算来加速，而不必每个位置单独计算。

复杂度

时间

压缩状态 O(N) 。

状态数量 O(2^N) ，状态变化 O(1) ，总共 O(2^N) 。

计算目标状态 O(1) 。

解压状态 O(N) 。

总时间复杂度为 O(2^N) 。

附上代码：

 1 #include <betss/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int MaxN = 16;
 6 const int MaxL = 1 << 16;
 7 
 8 int l[MaxL], p[MaxL];
 9 int n, m, x;
10 long long b;
11 
12 int main() {
13   cin >> n >> b;
14   for (int i = 0; i < n; i++) {  // 压缩表示
15     cin >> x;
16     l[1] |= x << i;
17   }
18   for (m = 1; !p[l[m]]; m++) {                                           // 寻找循环节
19     p[l[m]] = m;                                                         // 记录位置
20     l[m + 1] = l[m] ^ (l[m] << 1 & ((1 << n) - 1)) ^ (l[m] >> (n - 1));  // n位循环左移取与
21   }
22 
23   if (++b >= m) {  // 超出循环节的部分取余
24     b = (b - p[l[m]]) % (m - p[l[m]]) + p[l[m]];
25   }
26   for (int i = 0; i < n; i++) {  // 拆分输出
27     cout << (l[b] >> i & 1) << endl;
28   }
29   return 0;
30 }