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

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

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

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

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

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

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

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

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

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

AC代碼片段如下：

結(jié)合代碼更好理解一點(diǎn)

 #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ù)個(gè)數(shù)int k;				//k進(jìn)制 int l;  			//l位數(shù) int main(){	ll sum=0;				//總計(jì) 	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ù),動(dòng)態(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;}