题解 P2203 【Blink】

jiang_cheng · 2021-02-05 14:13:28 · 题解

解题思路：

打模拟赛的一道题可我考试时没写出来，这道题b的数据很大，肯定是有循环节的，于是就压缩表示，并找循环节就出来了。（管理员大大最帅了，让我过吧！！！）

附上代码：

#include <cstdio>
#include <iostream>

using namespace std;

const int kMaxN = 16;
const int kMaxL = 1 << 16;

int l[kMaxL], p[kMaxL];
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;
}