学步园

当 K=10,N=1时，结果为9，K=10,N=2时，结果为90，K=10,N=3时，结果为891.
我们可以想到无论K为何值，N=1时，结果为K-1，无论K为何值，N=2时，结果为K^2-K，因为K^2为最小的三位数，所有的两位数肯定都满足题目中不连续出现两个0的条件，让最小的三位数减去K进制下一位数的个数(K-1)再减去多加的那个1，就是满足条件两位数的个数。
如果是N位数咱们该如何计算呢，首先知道我们分析数字的组成，我们发现可以分为两种情况。
当最后一位不为0时结果为f(N-1)*(K-1),其中f(N-1)为N-1位时满足要求的所有数字个数，(K-1)为最后一位可能的情况。
当最后一位为0时，那么倒数第二位不可能为0，这种情况下总个数为f(N-2)*(K-1),就相当于求N-1位数最后一位不为0并满足条件的个数。
所以f(N)=f(N-1)*(K-1)+f(N-2)*(K-1)
关于0是不是一位数此题默认的是不是一位数，那f(0)根据题目中的公式可知f(0)=1,不过谁知道0位数有几个啊。。。

#include <iostream>
#include <string>
using namespace std;

int sum[18];
int N, K;

int main()
{
	scanf("%d%d", &N, &K);
	sum[1] = K - 1;
	sum[2] = K * K - K;
	for(int i = 3; i <= N; i++)
	{
		sum[i] = (sum[i-1] + sum[i-2]) * (K - 1);
	}
	printf("%d\n", sum[N]);
	return 0;
}

.