首页 > 阿里3.6笔试 第一道 数学推导思路 时间复杂度O(n)
头像
酱天小禽兽
编辑于 2021-03-07 17:57
+ 关注

阿里3.6笔试 第一道 数学推导思路 时间复杂度O(n)

题目描述:输入n,对于n行3列的矩阵,每个位置放入数字1、2、3中的任意一个,但要保证每个位置的数字与其上下左右不能相同,数字选取次数无限制,输出一共有多少种排列的可能性。

只看第一行的话,只有两种大情况,
1:三个数都不一样(如1 2 3),这种情况有6种。
2:三个数中有两个一样(如 1 2 1),这种情况有6种。

当n-1行 为第一种情况时,如 1 2 3,可手算出n行的可能性:
第一种: 2 3 1     3  1  2       ——2种
第二种: 2 1 2     2  3  2       ——2种
其他情况如 1 3 2等,可以此类推。

当n-1行 为第二种情况时,如 1 2 1,可手算出n行的可能性:
第一种: 2 3 1     3  1  2            ——2种
第二种: 2 1 2     2  3  2     3  1  3    ——3种
其他情况如 2 1 2等,可以此类推。

之后就可以从上往下递推了。
设第n-1行第一种情况有n种,第二种情况有m种,那么第n行第一种情况有2n+2m种,第二种情况有2n+3m种,递推到最后一行取余即可。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        while (t-- > 0) {
            int num = scanner.nextInt();

            long n = 6;
            long m = 6;
            for (int i = 0; i < num - 1; i++) {
                long newn = (n * 2) % 1000000007 + (m * 2) % 1000000007;
                long newm = (n * 2) % 1000000007 + (m * 3) % 1000000007;
                n = newn % 1000000007;
                m = newm % 1000000007;
            }

            System.out.println((n + m) % 1000000007);
        }
    }
}


全部评论

(5) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐