题目链接：https://www.acwing.com/problem/content/1962/

题解

对于16个灯泡，只有\(2^{16}\)种状态，可以用int存下来。时间t最大是\(10^{15}\)，如果全部遍历则会超时。但是每个时间t都是一个状态，而状态数最大只有\(2^{16}\)，所以在某个时间一定会有一个出现过的状态，然后形成一个循环节，这时候只需要用剩下的时间对循环节长度取余就能找到，到达最终相同状态所需的时间。

代码

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100000;
LL n,a,b;
LL p[N];

int update(int state) {
    int ans = 0;
    for (int i = 0; i < n; i ++ ) {
        int k = (i + 1) % n;
        ans |= ((state >> i & 1) ^ (state >> k & 1)) << i;
    }
    return ans;
}

void print(int state) {
    for (int i = n - 1; i >= 0 ; i -- ) {
        cout << (state >> i & 1) << endl;
    }
}
int main()
{
    int state=0;
    cin >> n >> b;
    for (int i = n-1 ; i >= 0 ; i -- ) {
        cin >> a;
        state |= a << i;
    }
    
    memset(p,-1,sizeof p);
    p[state] = 0;
    
    for (int i = 1; ; i ++ ) {
        state = update(state);
        if(i == b) {
            print(state);
            break;
        }
        else if(p[state] == -1) p[state] = i;
        else {
            int r = ( b - i ) % (i - p[state]);
            while(r -- ) state = update(state);
            print(state);
            break;
        }
    }
    return 0;
}