题意整理

• 给定长度为n的格子，要在格子里填入1、2、3、4这四个数。
• 每个数填入的次数不限，但要求偶数填入的次数必须是偶数次。
• 求总共有多少种方案。

方法一（动态规划）

1.解题思路

• 状态定义：$dp\left[i\right]\left[0\right]dp[i][0]$dp[i][0]表示前i个格子中有偶数个2、偶数个4；$dp\left[i\right]\left[1\right]dp[i][1]$dp[i][1]表示前i个格子中有偶数个2、奇数个4；$dp\left[i\right]\left[2\right]dp[i][2]$dp[i][2]表示前i个格子中有奇数个2、偶数个4；$dp\left[i\right]\left[3\right]dp[i][3]$dp[i][3]表示前i个格子中有奇数个2、奇数个4。
• 状态初始化：第一个格子为1或3时，没有2和4，所以$dp\left[1\right]\left[0\right]=2dp[1][0]=2$dp[1][0]=2；第一个格子为4时，有偶数个2、奇数个4，所以$dp\left[1\right]\left[1\right]=1dp[1][1]=1$dp[1][1]=1；第一个格子为2时，有奇数个2、偶数个4，所以$dp\left[1\right]\left[2\right]=1dp[1][2]=1$dp[1][2]=1；第一个格子无论怎么放，也无法满足奇数个2、奇数个4，所以$dp\left[1\right]\left[3\right]=0dp[1][3]=0$dp[1][3]=0。
• 状态转移：每一个状态由2的数目是奇数还是偶数、4的数目是奇数还是偶数组成，每次多放一个数，只能改变2的奇偶或者4的奇偶的其中一个，所以如果两个的奇偶完全相反时，则状态无法转移，其它的情形都可以。于是有$dp\left[i\right]\left[0\right]=2\ast dp[i-1]\left[0\right]+dp[i-1]\left[1\right]+dp[i-1]\left[2\right]dp[i][0]=2*dp[i-1][0]+dp[i-1][1]+dp[i-1][2]$dp[i][0]=2∗dp[i−1][0]+dp[i−1][1]+dp[i−1][2]，$dp\left[i\right]\left[1\right]=dp[i-1]\left[0\right]+2\ast dp[i-1]\left[1\right]+dp[i-1]\left[3\right]dp[i][1]=dp[i-1][0]+2*dp[i-1][1]+dp[i-1][3]$dp[i][1]=dp[i−1][0]+2∗dp[i−1][1]+dp[i−1][3]，$dp\left[i\right]\left[2\right]=dp[i-1]\left[0\right]+2\ast dp[i-1]\left[2\right]+dp[i-1]\left[3\right]dp[i][2]=dp[i-1][0]+2*dp[i-1][2]+dp[i-1][3]$dp[i][2]=dp[i−1][0]+2∗dp[i−1][2]+dp[i−1][3]，$dp\left[i\right]\left[3\right]=dp[i-1]\left[1\right]+dp[i-1]\left[2\right]+2\ast dp[i-1]\left[3\right]dp[i][3]=dp[i-1][1]+dp[i-1][2]+2*dp[i-1][3]$dp[i][3]=dp[i−1][1]+dp[i−1][2]+2∗dp[i−1][3]。

当测试数据过大时，会报堆内存溢出。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;
    public int GetNumberOfSchemes (int n) {
        int[][] dp=new int[n+1][4];
        /*dp[i][0]表示偶数个2、偶数个4
        dp[i][1]表示偶数个2、奇数个4
        dp[i][2]表示奇数个2、偶数个4
        dp[i][3]表示奇数个2、奇数个4*/
        //第一个格子为1或3
        dp[1][0]=2;
        //第一个格子为4
        dp[1][1]=1;
        //第一个格子为2
        dp[1][2]=1;
        //没有满足条件的情况
        dp[1][3]=0;
        //状态转移
        for(int i=2;i<=n;i++){
            dp[i][0]=((2*dp[i-1][0]%mod+dp[i-1][1])%mod+dp[i-1][2])%mod;
            dp[i][1]=((dp[i-1][0]+2*dp[i-1][1]%mod)%mod+dp[i-1][3])%mod;
            dp[i][2]=((dp[i-1][0]+2*dp[i-1][2]%mod)%mod+dp[i-1][3])%mod;
            dp[i][3]=((dp[i-1][1]+dp[i-1][2])%mod+2*dp[i-1][3]%mod)%mod;
        }
        return dp[n][0];
    }
    
}

3.复杂度分析

• 时间复杂度：循环总共执行$n-1n-1$n−1次，所以时间复杂度为$O\left(n\right)O(n)$O(n)。
• 空间复杂度：需要额外$4\ast (n+1)4*(n+1)$4∗(n+1)的空间，所以空间复杂度为$O\left(n\right)O(n)$O(n)。

方法二（数学）

1.解题思路

可以按偶数出现的次数进行分类讨论。

• 如果2、4出现0次，总共有$2^{n}2^n$2n种方案，每个格子要么选1，要么选3。
• 如果2、4出现2次，总共有$2^{n-2}\ast C_n^2\ast 22^\{n-2\}*C\_n^2*2$2n−2∗Cn2​∗2种方案，先在n个格子选2个放入2、2（或4、4），然后剩下n-2个格子里放1和3。
• 如果2、4出现4次，总共有$2^{n-4}\ast C_n^4\ast (C_4^0+C_4^2+C_4^4)2^\{n-4\}*C\_n^4*(C\_4^0+C\_4^2+C\_4^4)$2n−4∗Cn4​∗(C40​+C42​+C44​)种方案，先在n个格子选4个放入2、4，放入2、4的方式总共有$C_4^0+C_4^2+C_4^{4}C\_4^0+C\_4^2+C\_4^4$C40​+C42​+C44​种，然后剩下n-4个格子里放1和3。
• 如果2、4出现6次，总共有$2^{n-6}\ast C_n^6\ast (C_6^0+C_6^2+C_6^4+C_6^6)2^\{n-6\}*C\_n^6*(C\_6^0+C\_6^2+C\_6^4+C\_6^6)$2n−6∗Cn6​∗(C60​+C62​+C64​+C66​)种方案，先在n个格子选6个放入2、4，放入2、4的方式总共有$C_6^0+C_6^2+C_6^4+C_6^{6}C\_6^0+C\_6^2+C\_6^4+C\_6^6$C60​+C62​+C64​+C66​种，然后剩下n-6个格子里放1和3。
• 依此类推，一直算到2、4出现次数为最大的小于等于n的偶数为止。总方案数为：$2^n+2^{n-2}\ast C_n^2\ast 2+2^{n-4}\ast C_n^4\ast (C_4^0+C_4^2+C_4^4)+2^{n-6}\ast C_n^6\ast (C_6^0+C_6^2+C_6^4+C_6^6)+\dots \dots 2^n+2^\{n-2\}*C\_n^2*2+2^\{n-4\}*C\_n^4*(C\_4^0+C\_4^2+C\_4^4)+2^\{n-6\}*C\_n^6*(C\_6^0+C\_6^2+C\_6^4+C\_6^6)+\dots \dots$2n+2n−2∗Cn2​∗2+2n−4∗Cn4​∗(C40​+C42​+C44​)+2n−6∗Cn6​∗(C60​+C62​+C64​+C66​)+……，由于$C_n^0+C_n^2+C_n^4+\dots \dots C\_n^0+C\_n^2+C\_n^4+\dots \dots$Cn0​+Cn2​+Cn4​+……的值不管n为奇数，还是偶数，都是$2^{n-1}2^\{n-1\}$2n−1，所以总方案数转化为：$2^n\ast 2^0+2^{n-2}\ast C_n^2\ast 2^1+2^{n-4}\ast C_n^4\ast 2^3+2^{n-6}\ast C_n^6\ast 2^5+\dots \dots 2^n*2^0+2^\{n-2\}*C\_n^2*2^1+2^\{n-4\}*C\_n^4*2^3+2^\{n-6\}*C\_n^6*2^5+\dots \dots$2n∗20+2n−2∗Cn2​∗21+2n−4∗Cn4​∗23+2n−6∗Cn6​∗25+……再化简得：$2^{n-1}\ast 2+2^{n-1}\ast C_n^2+2^{n-1}\ast C_n^4+2^{n-1}\ast C_n^6+\dots \dots 2^\{n-1\}*2+2^\{n-1\}*C\_n^2+2^\{n-1\}*C\_n^4+2^\{n-1\}*C\_n^6+\dots \dots$2n−1∗2+2n−1∗Cn2​+2n−1∗Cn4​+2n−1∗Cn6​+……，合并$2^{n-1}2^\{n-1\}$2n−1得：$2^{n-1}\ast (1+C_n^0+C_n^2+C_n^4+C_n^6+\dots \dots )2^\{n-1\}*(1+C\_n^0+C\_n^2+C\_n^4+C\_n^6+\dots \dots )$2n−1∗(1+Cn0​+Cn2​+Cn4​+Cn6​+……)，所以总方案数为：$2^{n-1}\ast (1+2^{n-1})2^\{n-1\}*(1+2^\{n-1\})$2n−1∗(1+2n−1)。

计算$2^{n-1}2^\{n-1\}$2n−1可能会溢出，可以通过快幂法避免。

动图展示（快幂法）：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;
    public int GetNumberOfSchemes (int n) {
        //快幂法计算2的n-1次幂
        long num=fastpow(2,n-1);
        //计算方案数
        num=(num*(num+1))%mod;
        return (int)num;
    }
    
    //快幂法
    private long fastpow(long base,int k){
        long res=1;
        while(k!=0){
            //如果k是奇数，将res乘上base
            if(k%2==1){
                res=(res*base)%mod;
            }
            //每次base翻倍，k减半
            base=(base*base)%mod;
            k>>=1;
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：快幂法需要执行$lo{g}_{2}nlog\_2n$log2​n次运算，所以时间复杂度为$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O\left(1\right)O(1)$O(1)。