问题： 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字， 那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候， 所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对 1000000007取模后的值。 输入格式 输入包含两个正整数，K和L。 输出格式 输出一个整数，表示答案对1000000007取模后的值。 样例输入 4 2 样例输出 7 分析： 1.L位：是指数的长度是L位 2.K进制：进制为K（最大的那个数字是K-1） 3.由0~k-1中的数字组成的数 4.相邻位数不连续则满足条件 5.统计总个数对1000000007取模后输出
数据规模与约定: 对于30%的数据，K^L <= 10^6； 对于50%的数据，K <= 16， L <= 10； 对于100%的数据，1 <= K,L <= 100。 /** @author Mingxu_Deng @version 2020-10-4下午03:52:40 问题： 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字， 那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候， 所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对 1000000007取模后的值。 输入格式 输入包含两个正整数，K和L。 输出格式 输出一个整数，表示答案对1000000007取模后的值。 样例输入 4 2 样例输出 7 分析： 1.L位：是指数的长度是L位 2.K进制：进制为K（最大的那个数字是K-1） 3.由0~k-1中的数字组成的数 4.相邻位数不连续则满足条件 5.统计总个数对1000000007取模后输出 数据规模与约定: 对于30%的数据，K^L <= 10^6； 对于50%的数据，K <= 16， L <= 10； 对于100%的数据，1 <= K,L <= 100。 */ public class ALG_003_KGoodNumber { public static void main(String[] args) { int K,L,i,j,a,count=0; Scanner s = new Scanner(System.in); K = s.nextInt();L = s.nextInt(); //创建 L 位 K 进制的二维数组 int[][] arr = new int[L+1][K]; for(i = 0;i<K;i++){//因为每个 0~K 之间的数在第一个位置上都只有一种可能，故在第一行的每个位置赋值为1 arr[1][i] = 1; } for(i = 2;i<=L;i++){// for 循环，从第二行开始，直到 L 行结束（包括第L行） for(j=0;j<K;j++){// for 循环，每个位置上的数都只能是 0~K 之间的数 for(a=0;a<K;a++){//同时在 0~K 之间对数组遍历，进行筛选 if(a!=j-1 && a!=j+1){//如果满足 K 好数的条件 //则把二维数组中最后一行的值改为每一列可能性的总值 arr[i][j] += arr[i-1][a]; //取模存放，避免占用内存过大 arr[i][j] %= 1000000007; } } } } //对数组中的每一列的结果总值进行汇总(同时用1000000007取模，以保证输出结果的正确性) for(i=1;i<K;i++){ count += arr[L][i]; count %= 1000000007; } System.out.println(count); } }