对蓝桥杯算法练习 003 K好数的理解

阳光穿透心脏的1/2处 2022-12-12 01:53 122阅读 0赞

## ALG\_003\_K好数 ##

问题：  
如果一个自然数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);
    		}
    }