题目的主要信息：

• 长为n的连续格子，要在格子里面填上1、2、3、4这四个数字
• 要求同一个偶数出现的次数也是偶数次，即2出现偶数次，4也要出现偶数次
• 求填充的方案种数，要对答案取模1e9+7

方法一：动态规划（超时）

具体做法：

我们可以用动态规划来表示，建立数组dp，其中：

$dp[i][0]dp[i][0]$表示填充长度为$ii$的格子，2出现偶数次且4出现偶数次的方案数，初始时一个格子有填充1或者3两种方案；

$dp[i][1]dp[i][1]$表示填充长度为$ii$的格子，2出现奇数次且4出现奇数次的方案数，初始时一个格子，没有填充方案；

$dp[i][2]dp[i][2]$表示填充长度为$ii$的格子，2出现偶数次且4出现奇数次的方案数，初始时一个格子，可以选择填充1个4的一种方案；

$dp[i][3]dp[i][3]$表示填充长度为$ii$的格子，2出现奇数次且4出现偶数次的方案数，初始时一个格子，可以选择填充1个2的一种方案；

状态转移的时候，我们可以遍历$22$到$nn$，每次查看第$ii$项的前一项，2出现偶数次且4出现偶数次的情况可以由前一个的2出现偶数次且4出现偶数次后面接1或者3实现，也可以由2出现偶数次且4出现奇数次的情况末尾加一个4实现，还可以由2出现奇数次且4出现偶数次的情况末尾加一个2实现，于是我们就有状态转移方程：

$dp[i][0]=2\ast dp[i-1][0]+dp[i-1][2]+dp[i-1][3]dp[i][0]\; =\; 2\; *\; dp[i-1][0]\; +\; dp[i\; -\; 1][2]\; +\; dp[i\; -\; 1][3]$

同理，我们可以用相同的推断方式得到另外三种情况的转移方程：

$dp[i][1]=2\ast dp[i-1][1]+dp[i-1][2]+dp[i-1][3]dp[i][1]\; =\; 2\; *\; dp[i-1][1]\; +\; dp[i\; -\; 1][2]\; +\; dp[i\; -\; 1][3]$

$dp[i][2]=dp[i-1][0]+dp[i-1][1]+2\ast dp[i-1][2]dp[i][2]\; =\; dp[i-1][0]\; +\; dp[i\; -\; 1][1]\; +\; 2\; *\; dp[i\; -\; 1][2]$

$dp[i][3]=dp[i-1][0]+dp[i-1][1]+2\ast dp[i-1][3]dp[i][3]\; =\; dp[i-1][0]\; +\; dp[i\; -\; 1][1]\; +\; 2\; *\; dp[i\; -\; 1][3]$

我们也发现了，上面状态转移只用到了$ii$和它前面的$i-1i-1$项，于是我们可以用滚动数组，缩小使用的空间。

class Solution {
public:
    int mod = 1e9 + 7;
    int GetNumberOfSchemes(int n) {
        vector<vector<long> > dp(2, vector<long>(4, 0)); //防止超出不及时取模，用long
        int k = 0;
        dp[0][0] = 2; //第一个格子偶数个2且偶数个4，即1或者3
        dp[0][1] = 0; //第一个格子奇数个2且奇数个4，不可能，无
        dp[0][2] = 1; //第一个格子偶数个2且奇数个4，即4
        dp[0][3] = 1; //第一个格子奇数个2且偶数个4，即2
        for(int i = 2; i <= n; i++){ //根据上述依次添加前一个
            k = 1 - k;  //滚动数组
            dp[k][0] = (2 * dp[1 - k][0] + dp[1 - k][2] + dp[1 - k][3]) % mod;
            dp[k][1] = (2 * dp[1 - k][1] + dp[1 - k][2] + dp[1 - k][3]) % mod;
            dp[k][2] = (dp[1 - k][0] + dp[1 - k][1] + 2 * dp[1 - k][2]) % mod;
            dp[k][3] = (dp[1 - k][0] + dp[1 - k][1] + 2 * dp[1 - k][3]) % mod;
        }
        return dp[k][0];
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，从2遍历到$nn$
• 空间复杂度：$O(1)O(1)$，辅助数组dp只有8个空间，属于常数级

方法二：矩阵快速幂

具体做法：

我们已经有了方法一的转移方程了，可以将其转化为矩阵乘法如下：

我们只要求和基础矩阵的$n-1n-1$次方与初始值的乘积矩阵，去第一个元素即是我们要的答案。 矩阵的次方我们可以采用矩阵快速幂：

使用类似二分的方法来计算矩阵的幂，每次只需要计算2、4、8、16……级别的次方，其他的次方都有前面算的得到。

class Solution {
public:
    int mod = 1e9 + 7;
    vector<vector<long>> base = { //由刚刚推算出的基础矩阵
        {2, 0, 1, 1},
        {0, 2, 1, 1},
        {1, 1, 2, 0},
        {1, 1, 0, 2}
    };
    vector<vector<long>> Mul(vector<vector<long>>& x, vector<vector<long>>& y){ //x矩阵乘上y矩阵
        int n = y[0].size(); //查看第二维是1还是4
        vector<vector<long>> res(4, vector<long>(n, 0));
        for(int i = 0; i < 4; i++){ //遍历相乘相加
            for(int j = 0; j < n; j++){
                for(int k = 0; k < 4; k++){
                    res[i][j] = (res[i][j] + x[i][k] * y[k][j]) % mod;
                }
            }
        }
        return res;
    }
    vector<vector<long>> Pow(vector<vector<long>>& x, int k){ //矩阵快速幂
        vector<vector<long>> res(4, vector<long>(4, 0));
        for(int i = 0; i < 4; i++)
            res[i][i] = 1; //初始化为单位矩阵
        while(k){
            if(k & 1)
                res = Mul(res, base);
            k = k >> 1;
            base = Mul(base, base);
        }
        return res;
    }
    int GetNumberOfSchemes(int n) {
        vector<vector<long>> a = base;
        vector<vector<long>> b = {{2},{0},{1},{1}};
        vector<vector<long>> c = Pow(a, n - 1); //基础矩阵的n-1次方
        return (int)Mul(c, b)[0][0]; //二者相乘
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，矩阵快速幂一共调用$O(2\ast lo{g}_{2}n)O(2*log\_2n)$次乘法运算，每次乘法中要运算$6464$次
• 空间复杂度：$O(1)O(1)$，辅助矩阵的大小为16，常数级空间

方法三：数学规律

具体做法：

观察前几项的规律，我们可以得到直接表达式而非递推公式：

$2^{n-1}\ast (1+2^{n-1})2^\{n-1\}*(1+2^\{n-1\})$

我们可以用快速幂加上快速乘法，快速计算这个公式。快速幂和快速乘法参考这里。

class Solution {
public:
    int mod = 1e9 + 7;
    long fast(long x, long y){ //快速乘法
        long res = 0;
        x %= mod;
        y %= mod;
        while(y){
            if(y & 1){
                res += x; //加法代替乘法，防止爆long
                if(res >= mod)
                    res -= mod;
            }
            y = y >> 1;
            x = x << 1;
            if(x >= mod)
                x -= mod;
        }
        return res;
    }
    long Pow(long x, long y){ //快速幂
        long res = 1;
        while(y){
            if(y & 1) //可以再往上乘一个
                res = fast(res, x);
            x = fast(x, x); //叠加
            y = y >> 1; //减少乘次数
        }
        return res;
    }
    int GetNumberOfSchemes(int n) {
        if(n == 1)
            return 2;
        //快速幂算次方
        long x = Pow(2, n - 1);
        long y = Pow(2, 2 * n - 2);
        return (x + y) % mod;
    }
};

复杂度分析：

• 时间复杂度：$O((lo{g}_{2}n{)}^2)O((log\_2n)^2)$，不管是快速幂还是快速乘法都是$O(lo{g}_{2}n)O(log\_2n)$，这里嵌套使用
• 空间复杂度：$O(1)O(1)$，常数级空间