题解 P2203 【Blink】

信守天下 · 2021-02-05 10:47:55 · 题解

思路：寻找循环节

因为有16盏灯，数据范围为10^{15}

很明显，这道题一次一次模拟会超时

数据上限是16盏灯，就只有16!种可能

因为10^{15} > 16!,所以这道题一定有循环节

所以思路就是记录状态，然后找循环节

所有的状态都可以压缩表示成一位进行优化

code

#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;
}