题目描述

8 间牢房排成一排，每间牢房不是有人住就是空着。

每天，无论牢房是被占用或空置，都会根据以下规则进行更改：

• 如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
• 否则，它就会被空置。

（请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）

我们用以下方式描述监狱的当前状态：如果第 i 间牢房被占用，则 cell[i] == 1，否则 cell[i] == 0。

根据监狱的初始状态，在 N 天后返回监狱的状况（和上述 N 种变化）。

样例

输入：cells = [0,1,0,1,1,0,0,1], N = 7
输出：[0,0,1,1,0,0,0,0]
解释：
下表概述了监狱每天的状况：
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

输入：cells = [1,0,0,1,0,0,1,0], N = 1000000000
输出：[0,0,1,1,1,1,1,0]

注意

• cells.length == 8
• cells[i] is in {0, 1}
• 1 <= N <= 10^9

算法1

(矩阵乘法，快速幂) $O(m^3 \log N)$

假设格子的数目为 $m$ 个，下标从 0 开始。

1. 我们用一个 $(m + 1) \times (m + 1)$ 的矩阵 $A$ 来描述每一次变化。假设 cells 是一个 $(m+1)$ 的列向量，其中 cells[m] 始终为 1，则 $A \times cells$ 在模 2 意义下的矩阵乘法相当于做了一次变换。
2. 下面构造 $A$ 矩阵：由于在每次变化中，首尾两个格子始终保持 0，则 A[0][i] 和 A[m - 1][i] 两行全为 0；从第 1 行到第 m - 2 行，每行中 A[i][i - 1]，A[i][i + 1] 和 A[i][m] 为 1，其余为 0。这是因为我们每次的变化是，每个格子与相邻两个格子有关，但简单的做模 2 的加法状态是相反的，因此需要一个常数 1 来修正。最后，第 m 行中，A[m][m] 为 1。
3. 做 $N$ 次变换相当于 $A^N \times cells$，利用结合律，我们可以用快速幂计算 $tot = A^N$，最后 $tot \times cells$ 就是答案。

时间复杂度

• 每次矩阵乘法的时间复杂度为 $O(m^3)$，快速幂为 $O(\log N)$ 次乘法，故总时间复杂度为 $O(m^3 \log N)$。

C++ 代码

vector<vector<int>> operator * (const vector<vector<int>> &x, const vector<vector<int>> &y) {
        int n = x.size();
        vector<vector<int>> z(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    z[i][j] = (z[i][j] + x[i][k] * y[k][j]) & 1;

        return z;
}

class Solution {
public:

    vector<vector<int>> power(const vector<vector<int>> &x, int y) {
        int n = x.size();
        vector<vector<int>> tot(n, vector<int>(n, 0)), p = x;
        for (int i = 0; i < n; i++)
            tot[i][i] = 1;

        for (; y; y >>= 1) {
            if (y & 1) {
                tot = tot * p;
            }
            p = p * p;
        }

        return tot;
    }

    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        int m = cells.size();
        vector<vector<int>> A(m + 1, vector<int>(m + 1, 0)), tot;
        vector<int> ans(m, 0);

        for (int i = 1; i < m - 1; i++)
            A[i][i - 1] = A[i][i + 1] = A[i][m] = 1;

        A[m][m] = 1;

        tot = power(A, N);

        ans[0] = ans[m - 1] = 0;

        for (int i = 1; i < m - 1; i++) {
            int tmp = tot[i][m];
            for (int j = 0; j < m; j++)
                tmp += tot[i][j] * cells[j];

            ans[i] = tmp & 1;
        }

        return ans;
    }
};

算法2

(哈希表) $O(m \cdot 2^m)$

1. 题目中说格子的个数始终为 8 个，则在 N 天的过程中，必然会出现循环节，循环节的长度不超过 256。
2. 我们开一个长度为 256 的哈希数组来记录某个情况最早出现在哪天。
3. 假设变化过程中，第 i 次的变化和第 h (< i) 天的变化后是一致的，则循环节的长度为 $l = i - h$，我们可以跳过若干个循环节，然后再处理结尾部分即可。

时间复杂度

• 循环节的长度最大为 $O(2^m)$，每次需要 $O(m)$ 的时间更新，故总时间复杂度为 $O(m \cdot 2^m)$。

C++ 代码

class Solution {
public:

    vector<int> nextDay(const vector<int>& cells) {
        int m = cells.size();
        vector<int> ans(m, 0);
        for (int i = 1; i < m - 1; i++)
            ans[i] = 1 - (cells[i - 1] ^ cells[i + 1]);
        return ans;
    }

    int getHash(const vector<int>& cells) {
        int m = cells.size(), tot = 0;
        for (int i = 0; i < m; i++)
            if (cells[i])
                tot += 1 << i;

        return tot;
    }

    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        int m = cells.size();
        vector<int> vis(1 << m, -1);

        vis[getHash(cells)] = 0;

        for (int i = 1; i <= N; i++) {
            cells = nextDay(cells);
            int h = getHash(cells);
            if (vis[h] != -1) {
                int l = i - vis[h];
                i = N - (N - vis[h]) % l;
            }
            vis[h] = i;
        }

        return cells;
    }
};