藍橋杯 ALGO-3 K好數

解題思路：

如果不是最高位，那麼可以用0至k-1這k個數來填充某位，則i位j進制的好數個數會有d[i][j] 個（i表示第i位，j表示此位所填的數），最後将0-k-1這k種情況的d[i][j]的值相加起來,得到答案。

狀态轉移方程：d[i][j]=∑d[i-1][q]   (q!=j±1,0<=q<k,i>1)。

初始化：d[1][j]=1(0<=j<k)。

對最高位要特殊處理，因為最高位不能為0。

AC代碼：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#define mod 1000000007
using namespace std;
__int64 d[105][105];
int main(){
	int i,j,k,l,q;
	__int64 ans=0;
	scanf("%d%d",&k,&l);
	for(i=0;i<k;i++)//一位時肯定不相鄰
		d[1][i]=1;
	for(i=2;i<=l;i++)
		for(j=0;j<k;j++)
			for(q=0;q<k;q++)

				if((q!=j+1)&&(q!=j-1))//根據題意，本位的數字與前面後面相鄰的數字是不能相等
					d[i][j]=(d[i][j]+d[i-1][q])%mod;
	for(i=1;i<k;i++)//最高位不能為0
		ans=(ans+d[l][i])%mod;
	printf("%I64d\n",ans%mod);
	return 0;
}