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

輸入包含兩個正整數(shù)，K和L。

對于30%的數(shù)據(jù)，KL <= 106；

對于50%的數(shù)據(jù)，K <= 16， L <= 10；

對于100%的數(shù)據(jù)，1 <= K,L <= 100。

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

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

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

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

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

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 位數(shù) 且 j為第一位的k好數(shù)個數(shù)int k;				//k進制 int l;  			//l位數(shù) 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位數(shù)的K好數(shù)    	}	for(int i=2;i<=l;i++){  		//從2位數(shù)到l位數(shù),動態(tài)規(guī)劃 		for(int j=0;j<k;j++){		//第一位數(shù)為j 			for(int f=0;f<k;f++){	//第二位數(shù)為f 				if(f+1!=j && f-1!=j){ //不是相鄰的數(shù)					dp[i][j] += dp[i-1][f];					dp[i][j] %= mod; 				} 			} 		} 	}	for(int j=1;j<k;j++){			//	去掉第一位為0的k好數(shù) 		sum += dp[l][j] ;		sum %= mod;	} 	cout<<sum;	return 0;}