寒假每日一题——闪烁（状态压缩）

闪烁

问题描述

农夫约翰对牛棚里昏暗的灯光感到不满，刚刚安装了一个新吊灯。

新吊灯由 N 个灯泡组成，这 N 个灯泡围成一圈，编号为 0∼N−1。

奶牛对这个新吊灯非常着迷，并且喜欢玩以下游戏：

对于第 i 个灯泡，如果在 T−1 时刻，它左侧的灯泡（当 i>0 时，为第 i−1 个灯泡；当 i=0 时，为第 N−1 个灯泡）是开着，那么在 T 时刻，就切换这个灯泡的状态。

这个游戏将持续 B 单位时间。

给定灯泡的初始状态，请确定在 B 单位时间后，它们的最终状态。

输入格式
第一行包含两个整数 N 和 B。

接下来 N 行，按顺序描述每个灯泡的初始状态，每行包含一个整数 1 （表示开）或 0（表示关）。

输出格式
共 N 行，按顺序每行输出一个灯泡的最终状态。

数据范围

• 3≤N≤16,
• 1≤B≤\(10^{15}\)

输入样例：

5 6
1
0
0
0
0

输出样例：

1
1
1
0
1

样例解释
灯泡状态如下：

时刻 T=0: 1 0 0 0 0
时刻 T=1: 1 1 0 0 0
时刻 T=2: 1 0 1 0 0
时刻 T=3: 1 1 1 1 0
时刻 T=4: 1 0 0 0 1
时刻 T=5: 0 1 0 0 1
时刻 T=6: 1 1 1 0 1

思路分析

完整代码

#include <bits/stdc++.h>
using namespace std;
int n;
long long m;
const int N = 1 << 16;
int p[N];

int upd(int state)
{
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int j = (i - 1 + n) % n;
        int x = state >> i & 1, y = state >> j & 1;
        res |= (x ^ y) << i;
    }
    return res;
}

void print(int state)
{
    for(int i = 0; i < n; i++)
    {
        cout << (state >> i & 1) << "\n" ;
    }
}

int main()
{
    cin >> n >> m;
    int state = 0;
    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        state |= x << i;
    }
    memset(p, -1, sizeof p);
    p[state] = 0;
    
    for(int i = 1; ; i++)
    {
        state = upd(state);
        if(i == m)
        {
            print(state);
            return 0;
        }
        else if(p[state] == -1) p[state] = i;
        else 
        {
            int len = i - p[state];
            int r = (m - i) % len;
            while(r--) state = upd(state);
            print(state);
            return 0;
        }
    }
}