P2203

mouseboy · 2022-10-28 17:41:45 · 题解

感谢 @cqbzpyl

[2024/10/23] 修复代码头文件问题

题意

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

思路

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

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

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

复杂度

时间

压缩状态 O(N) 。

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

计算目标状态 O(1) 。

解压状态 O(N) 。

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

附上代码：

#include <bets/stdc++.h>

using namespace std;

const int MaxN = 16;
const int MaxL = 1 << 16;

int l[MaxL], p[MaxL];
int n, m, x;
long long b;

int main() {
  cin >> n >> b;
  for (int i = 0; i < n; i++) {  // 压缩表示
    cin >> x;
    l[1] |= x << i;
  }
  for (m = 1; !p[l[m]]; m++) {                                           // 寻找循环节
    p[l[m]] = m;                                                         // 记录位置
    l[m + 1] = l[m] ^ (l[m] << 1 & ((1 << n) - 1)) ^ (l[m] >> (n - 1));  // n位循环左移取与
  }

  if (++b >= m) {  // 超出循环节的部分取余
    b = (b - p[l[m]]) % (m - p[l[m]]) + p[l[m]];
  }
  for (int i = 0; i < n; i++) {  // 拆分输出
    cout << (l[b] >> i & 1) << endl;
  }
  return 0;
}