如果一個自然數N的K進制表示中任意的相鄰的兩位都不是相鄰的數字，那么我們就說這個數是K好數。求L位K進制數中K好數的數目。例如K = 4，L = 2的時候，所有K好數為11、13、20、22、30、31、33 共7個。由于這個數目很大，請你輸出它對1000000007取模后的值。

輸入包含兩個正整數，K和L。

對于30%的數據，KL <= 106；

對于50%的數據，K <= 16， L <= 10；

對于100%的數據，1 <= K,L <= 100。

k好數思路:要得到所有的L位K進制數的k好數，我們需要先得到L-1位K進制數的k好數，再將其中第L位與第L-1位相鄰的數去掉即可。（子問題）

如果理解了上面那句話，那么我們只需要從1位開始遞推到L位的K進制數即可。

定義一個二維數組dp[i][j]，其中 i表示位數 j表示第一位數

即求出1位K進制數的k好數個數，dp[1][j],求出2位K進制數的k好數個數 dp[2][j]，如此遞推下去直到L位，

再將保存L位開頭從1到K-1的K進制的k好數相加

AC代碼片段如下：

結合代碼更好理解一點

 #include<iostream>#include<algorithm>#include<memory.h>using namespace std;#define mod 1000000007  typedef long long ll;ll dp[110][110];   //dp[i][j] 表示 i 位數 且 j為第一位的k好數個數int k;				//k進制 int l;  			//l位數 int main(){	ll sum=0;				//總計 	cin>>k>>l;	memset(dp,0,sizeof(dp));	for(int j=0;j<k;j++){			dp[1][j] =1;		//1位數的K好數    	}	for(int i=2;i<=l;i++){  		//從2位數到l位數,動態規劃 		for(int j=0;j<k;j++){		//第一位數為j 			for(int f=0;f<k;f++){	//第二位數為f 				if(f+1!=j && f-1!=j){ //不是相鄰的數					dp[i][j] += dp[i-1][f];					dp[i][j] %= mod; 				} 			} 		} 	}	for(int j=1;j<k;j++){			//	去掉第一位為0的k好數 		sum += dp[l][j] ;		sum %= mod;	} 	cout<<sum;	return 0;}