题目

问题描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值

输入格式
输入包含两个正整数，K和L。

输出格式
输出一个整数，表示答案对1000000007取模后的值。
样例输入

4 2

样例输出

7

数据规模与约定
对于30%的数据，KL <= 106；

对于50%的数据，K <= 16， L <= 10；

对于100%的数据，1 <= K,L <= 100。

题解

动态规划
动态规划最重要的就是找到状态转移方程
我们从 4 进制下 1 位长开始考虑
满足条件的数是 0，1，2，3
当 2 位长时，
满足条件的数 0-0，0-2，0-3，1-1，1-3，2-0，2-2，3-0，3-1，3-3，后 7 个即为解，即 0 后面可以跟 0、2、3，1 后面可以跟 1、3，2 后面可以跟 0、2，3 后面可以跟 0、1、3
当 3 位长时，
满足条件的数 00-0，00-2，00-3，02-0，02-2，03-0，03-1，03-3…可以发现其实还是我们前面找到的规律，即 0 后面可以跟 0、2、3，1 后面可以跟 1、3，2 后面可以跟 0、2，3 后面可以跟 0、1、3
我们可以反过来想，则
需要后面跟 0 的数其尾数只有 0，2，3
需要后面跟 1 的数其尾数只有 1，3
需要后面跟 2 的数其尾数只有 0，2
需要后面跟 3 的数其尾数只有 0，1，3

我们再把它抽象出来，可以得出结论：
对于字长为 i，最后一位是 j 的数，我们可以由子长为 i-1，最后一位是 k 的所有数求和得到，|j-k|!=1
所以得到状态转移方程：dp[ i ][ j ] = <math> <semantics> <mrow> <mo> ∑ </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> \sum </annotation> </semantics> </math>∑dp[ i-1 ][ k ] ( |j-k|!=1 )

#include<iostream>
using namespace std;
const int N = 205;  // 105要挂，我也不知道为什么
int main(){
	long long a[N][N];
	long long ans=0;
	int k,l;
	cin>>k>>l;
	// 初始化状态转移方程 
	for(int i=0;i<k;i++)
		a[1][i] = 1;
	for(int i=2;i<=l;i++) // 从第二位字长算起
		for(int j=0;j<k;j++)  // 最后一位是 j 的数
			for(int w=0;w<k;w++)   // 它是最后一位是 w 的数的总和
				if(w!=j-1 && w!=j+1){ 
					a[i][j] += a[i-1][w];
					a[i][j] %= 1000000007;
				}
	// 所以 k 进制的 K 好数，就是其 1-k 开头的所有数的和
	for(int j=1;j<k;j++){
		ans += a[l][j];
		ans %= 1000000007;
	} 
	cout<<ans;
	return 0;
}

查看题解目录