阿里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种
设第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);
}
}
}
京东一面79人在聊
投递用友等公司8个岗位 >