分析
本题数据范围N很小,B很大,从灯的所有状态来看,状态数一定是有限的,即最大不超过$2^N$,即65536。说明在枚举的过程中,对于状态集合来说有很多的重复状态。也就是有环。那么这道题就转换为一个枚举找环的问题。只需要不断枚举更新并记录状态,当发现某一个状态在之前出现过,就可以停止了。由于最大状态数有限,所以循环保证可以退出。
所以问题简化成下面一个例子:
0 1 2 3 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 … 4 5 6
枚举时当枚举到第二个4时,即找到了循环节。记录环的长度和初始位置即可。后面就可以通过很简单的位置偏移取模运算,找出6第一次出现的位置。
在实现的时候可以用一些小技巧,比如对状态用二进制压缩存储,而不用字符串或者数组,减小开销。包括涉及一些位运算操作,(判断某一位是否为1、反转某一位)
时间复杂度:$O(min(B, 2^N))$
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 65600;
int nums[N], idx = 0;
LL n, b;
void output(int x) {
for(int i = n - 1; i >= 0; i--) {
printf("%d\n", (x >> i & 1));
}
}
int main()
{
cin >> n >> b;
unordered_map<int, int> ump;
int x = 0, bit;
for(int i = 0; i < n; i++) {
cin >> bit;
x = x * 2 + bit;
}
ump[x] = 0;
nums[idx++] = x;
while(true) {
int tmp = x;
for(int i = 0; i < n; i++) {
int left = (i + 1) % n;
if(tmp >> left & 1) x ^= (1 << i);
}
if((LL)idx == b) {
output(x);
return 0;
}
if(ump.count(x)) break;
else {
ump[x] = idx;
nums[idx++] = x;
}
}
b = (b - ump[x]) % (idx - ump[x]) + ump[x];
output(nums[b]);
return 0;
}