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;

乘法溢出

虽然这里出入参都是int，但是在乘法过程中很容易超过int，在计算过程中使用long long，并随时取模即可

全部评论

推荐最新楼层

11-27 18:28

中南大学 Java

补录第一🗡，先斩teg

牛魔的秋招到现在第一次面腾讯，终于想起我了是吧全程1h，摆烂1个多月面试状态下滑严重强者发型面试官开局狠狠拷打实习经历就一实习难点展开讨论，最后发出灵魂拷打：“你这实习难点也不难啊，那我们问点基础的吧”。我最爱的八股环节（内容都包含在我整理的八股笔记专栏里https://www.nowcoder.com/discuss/660899447991201792?sourceSSR=users）1.什么是tcp的time_wait状态？time_wait状态有什么用？time_wait状态过多怎么解决？2.tcp的三次握手过程3.redis常用数据类型?zset底层原理？redis怎么看...

回不去家的废废在玉玉：云架平累的喔

查看5道真题和解析牛客创作赏金赛软件开发笔面经

点赞评论收藏

11-24 10:10

华中科技大学 Java

在拼多多工作的体验

首先，电梯真的是个大问题，等个电梯能等好久，尤其是饭点下楼，20到30分钟是常态。加班那么多，午休想休息一下，大家基本上都懒得出去吃饭，最后还是选择在公司吃。公司包四餐，早、中、晚和偶尔的夜宵（不是每天都有）。点餐得用系统，周五开放，能提前订下周的饭。要是没抢到好吃的，剩下的就只能将就了。其实餐食种类还挺丰富的，周边餐厅给拼多多供餐，但因为人多，好的餐很快就被抢光了。点餐后一定要按时去取，过了时间就算放弃，系统会记你的名字，几次不取就会被处罚。

拼多多集团-PDD公司福利 472人发布

点赞评论收藏

10-18 02:20

新疆理工学院网络工程师

秋招不知道咋搞了

双非二本，四级没过，秋招属于是一脸懵

鼗：四级有点难绷，感觉能拿国家励志奖学金，学习能力应该蛮强的，四级确实不重要，但是拿这个卡你可是很恶心啊

点赞评论收藏

11-24 15:09

已编辑

北京戏曲艺术职业学院硬件开发

华为报批

和对接人沟通确认意向，地点等信息，属于第一批。已经报批，结果会在12.5号前公布，最晚推迟两个周。武汉终端硬件电源，bg985本。苦等两个月，一定要给我发offer

沉淀一会：1.同学你面试评价不错，概率很大，请耐心等待； 2.你的排名比较靠前，不要担心，耐心等待； 3.问题不大，正在审批，不要着急签其他公司，等等我们！ 4.预计9月中下旬，安心过节； 5.下周会有结果，请耐心等待下； 6.可能国庆节前后，一有结果我马上通知你； 7.预计10月中旬，再坚持一下； 8.正在走流程，就这两天了； 9.同学，结果我也不知道，你如果查到了也告诉我一声； 10.同学你出线不明朗，建议签其他公司保底！ 11.同学你找了哪些公司，我也在找工作。

点赞评论收藏