2021-09-26 22:31 已编辑川大附小机械设计/制造

关注

题解 | #字符串的排列#

填数游戏

http://www.nowcoder.com/practice/4cce3022cab449039f0075e6665d53c7

题意

大小为 $n$ 的数组 $1\leq n \leq 10^9$
填入 $1,2,3,4$ 四个数字
求 $2$ 的个数为偶数， $4$ 的个数也为偶数的方案数。（这里题意不是很明确，通过看样例可以知道 $[2,4]$ 不满足题意）

方法

遍历+模拟

我们可以直接深度搜索所有的位置，填入 $1,2,3,4$ ，然后统计 $2,4$ 的个数

然而这种搜索所有的方案复杂度为状态数 $O(4^n)$ ，无法在时间复杂度内完成

通过合并 $1,3$ 两个值，可以把复杂度降低到 $O(3^n)$ ,但是依然无法在时间复杂度内完成

动态规划

基于上面的想法，我们同样把1和3进行合并。

令状态 $dp[i][j][k]$ 表示，从最开始到第 $i$ 个位置, 2出现的次数为 $j$ 次，4出现的次数为 $k$ 次的方案数

$dp[i][j][k] = 2dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1]$

然而这种做法，空间复杂度 $O(n^3)$ ，是无法接受的。注意到只关心2和4出现次数是否是偶数次，也就是次数模2后是否为0，因此可以对 $dp$ 的状态进行修改。

令状态 $dp[i][j][k]$ 表示，从最开始到第 $i$ 个位置, 2出现的次数模2后为 $j$ 次，4出现的次数模2后为 $k$ 次的方案数

$dp[i][j][k] = 2dp[i-1][j][k] + dp[i-1][(j+1)\bmod 2][k] + dp[i-1][j][(k+1)\bmod 2]$

这样空间复杂度为 下标 乘 取模的状态数(常数) 为 $O(n)$ ,

时间复杂度为 空间复杂度 乘 状态转移代价(常数) 为 $O(n)$ ，这题目的n最大达到 $10^9$ 依然无法在时间复杂度内完成

矩阵乘法

上面的方法虽然没有完成在时间复杂度内完成，但给出了相邻项的常数倍数的递推式

$dp[i][j][k] = 2dp[i-1][j][k] + dp[i-1][(j+1)\bmod 2][k] + dp[i-1][j][(k+1)\bmod 2]$

我们把 $j$ 和 $k$ 枚举展开

图片说明

$dp_{i,0,0} = 2dp_{i-1,0,0} + dp_{i-1,1,0} + dp_{i-1,0,1}$

$dp_{i,0,1} = 2dp_{i-1,0,1} + dp_{i-1,1,1} + dp_{i-1,0,0}$

$dp_{i,1,0} = 2dp_{i-1,1,0} + dp_{i-1,1,1} + dp_{i-1,0,0}$

$dp_{i,1,1} = 2dp_{i-1,1,1} + dp_{i-1,1,0} + dp_{i-1,0,1}$

把它写成矩阵的形式

$\begin{pmatrix} dp_{i,0,0} & dp_{i,0,1} & dp_{i,1,0} & dp_{i,1,1} \end{pmatrix} = \begin{pmatrix} dp_{i-1,0,0} & dp_{i-1,0,1} & dp_{i-1,1,0} & dp_{i-1,1,1} \end{pmatrix} \cdot \begin{pmatrix} 2 & 1 & 1 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}$

有矩阵乘法可得

$\begin{pmatrix} dp_{n,0,0} & dp_{n,0,1} & dp_{n,1,0} & dp_{n,1,1} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 2 & 1 & 1 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix} ^n$

由此，通过快速幂，我们可以在 $O(log(n))$ 的时间内计算出 $dp_{n,0,0}$ ，也就是要求的答案

只需要常数大小的空间 $O(1)$

代码

const int mod = 1000000007;
// a00 a01 a10 a11 
//                 2 1 1 0
//                 1 2 0 1
//                 1 0 2 1
//                 0 1 1 2
class Solution {
public:
    vector<vector<long long> > mul(vector<vector<long long>> &m1,vector<vector<long long>> &m2){
        vector<vector<long long> > r = vector<vector<long long>>(m1.size(),vector<long long>(m2[0].size(),0));
        for(int i = 0;i< m1.size();i++){
            for(int j = 0;j< m2[0].size();j++){
                for(int k = 0;k<m1[0].size();k++){
                    (r[i][j] += m1[i][k]*m2[k][j]%mod)%=mod;
                }
            }
        }
        return r;
    }
    vector<vector<long long> > mypow(int p){
        vector<vector<long long> > r = vector<vector<long long>>(4,vector<long long>(4,0));
        for(int i = 0;i<4;i++){
            r[i][i] = 1;
        }
        vector<vector<long long> > v = {
            {2, 1, 1, 0},
            {1, 2, 0, 1},
            {1, 0 ,2, 1},
            {0, 1, 1, 2}
        };

        while(p){
            if(p%2){
                r = mul(r,v);
            }
            v = mul(v,v);
            p/=2;
        }
        return r;
    }
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    // 要求每个偶数出现的次数也是偶数次
    int GetNumberOfSchemes(int n) {
        // write code here
        vector<vector<long long> > r = mypow(n);
        return r[0][0];
    }
};

递推变形

$dp_{i,0,0} = 2dp_{i-1,0,0} + dp_{i-1,1,0} + dp_{i-1,0,1}$

$dp_{i,0,1} = 2dp_{i-1,0,1} + dp_{i-1,1,1} + dp_{i-1,0,0}$

$dp_{i,1,0} = 2dp_{i-1,1,0} + dp_{i-1,1,1} + dp_{i-1,0,0}$

$dp_{i,1,1} = 2dp_{i-1,1,1} + dp_{i-1,1,0} + dp_{i-1,0,1}$

这里还可以合并 $dp$ 相同值的项来简化递推关系

我们注意到中间两项的和是可以合并的

$dp_{i,0,0} = 2dp_{i-1,0,0} + (dp_{i-1,1,0} + dp_{i-1,0,1})$

$dp_{i,0,1}+dp_{i,1,0} = 2(dp_{i-1,0,1}+dp_{i-1,1,0}) + 2dp_{i-1,1,1} + 2dp_{i-1,0,0}$

$dp_{i,1,1} = 2dp_{i-1,1,1} + (dp_{i-1,1,0} + dp_{i-1,0,1})$

这样对应的矩阵可以简化为

$\begin{pmatrix} 2 & 2 & 0 \\ 1 & 2 & 1 \\ 0 & 2 & 2 \\ \end{pmatrix}$

通过快速幂，我们可以在 $O(log(n))$ 的时间内计算出 $dp_{n,0,0}$ ，也就是要求的答案

只需要常数大小的空间 $O(1)$

代码

代码变为

const int mod = 1000000007;
// a00 a01+a10 a11 
//                2 2 0
//                1 2 1
//                0 2 2
class Solution {
public:
    vector<vector<long long> > mul(vector<vector<long long>> &m1,vector<vector<long long>> &m2){
        vector<vector<long long> > r = vector<vector<long long>>(m1.size(),vector<long long>(m2[0].size(),0));
        for(int i = 0;i< m1.size();i++){
            for(int j = 0;j< m2[0].size();j++){
                for(int k = 0;k<m1[0].size();k++){
                    (r[i][j] += m1[i][k]*m2[k][j]%mod)%=mod;
                }
            }
        }
        return r;
    }
    vector<vector<long long> > mypow(int p){
        vector<vector<long long> > r = vector<vector<long long>>(3,vector<long long>(3,0));
        for(int i = 0;i<3;i++){
            r[i][i] = 1;
        }
        vector<vector<long long> > v = {
            {2, 2, 0},
            {1, 2, 1},
            {0, 2 ,2}
        };

        while(p){
            if(p%2){
                r = mul(r,v);
            }
            v = mul(v,v);
            p/=2;
        }
        return r;
    }
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    // 要求每个偶数出现的次数也是偶数次
    int GetNumberOfSchemes(int n) {
        // write code here
        vector<vector<long long> > r = mypow(n);
        return r[0][0];
    }
};

注意到递推式中 $dp_{i,0,0}和dp_{i,1,1}$ 是满足轮换关系的，从技术上讲我们还可以继续合并简化，甚至推出一个非矩阵的表达式。但是这里不论是上面简化成三阶矩阵，还是继续简化，从思路来源上都是矩阵乘法，从时间复杂度上也没有差异，对于在给定时间内解题来说，在得到四阶矩阵递推时就已经可以了。

这里三阶和四阶矩阵是通过手推计算出的具体值，但是对于一些递推关系更复杂的题目，你可以用代码枚举1到4来计算这个具体的递推矩阵，从时间复杂度上只会多个常数倍数。最后只用关心一下初始矩阵的值。你需要保证的是相邻项的递推关系是与项数无关的常数即可。

数学/打表/OEIS

不论你通过上面反复简化 $dp$ 递推式，还是简单的把前面几项打表出来(2,6,20,72,272,1056)搜一下OEIS

你可以得到 $A063376:$

$a(-1) = 1$

对于 $n >= 0$ 有 $a(n) = 2^n + 4^n = 2^n \cdot (1 + 2^n)$

那么剩下的就是快速幂了

这道题在能推出的情况还是建议用矩阵写，或者手动推出数学表达式。对于一些难以推出递推式的题目，通过打表+观察或者OEIS，也许能给你带来解题的思路

通过快速幂，我们可以在 $O(log(n))$ 的时间内计算出要求的答案

只需要常数大小的空间 $O(1)$

代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    // 要求每个偶数出现的次数也是偶数次
    int GetNumberOfSchemes(int n) {
        const int mod = 1000000007;
        n-=1; // 起始项不同
        long long r = 1;
        long long v = 2;
        while(n){
            if(n%2)(r*=v)%=mod;
            (v*=v)%=mod;
            n/=2;
        }
        return r*(r+1)%mod;
    }
};

知识点

数学建模建立递推关系

在进入矩阵的推导之前，需要通过将题意数学建模，推导出一个动态规划的递推关系，这样才有助于我们发现其相邻项是常数倍数的加和关系，进而想到使用矩阵

快速幂与矩阵乘法

快速幂不论是矩阵乘法也好，还是普通的数值(例如上面我们得到的数学公式中2的幂次)，复数等等也罢，核心也就这么10行不到的代码，对于需要取mod的时候记住取模，

剩下的，实现其乘法部分即可。比如这里乘法部分是矩阵乘法。

        result = 1
        while(power){
            if(p%2){
                result = mul(result,base);
            }
            base = mul(base,base);
            power/=2;
        }
        return result;