题目描述:输入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); } } }
全部评论
(5) 回帖