P74156

K好数

难度 4 级小学动态规划入门进制转换线性 DP

讨论统计 0通过 1提交 0%通过率旧版界面

时间限制 1 秒 内存限制 256 MB

题目描述

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

输入

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

输出

输出一个整数，表示答案对1000000007取模后的值。

样例

样例 1

输入

4 2

输出

提示

数据规模与约定

锦囊1

使用动态规划。

锦囊2

用 $F_{ij}$ 表示长为 $i$ ，最后一位数字是 $j$ 的 $K$ 好数的个数，则 $F_{ij}$ =\sum F[i-1][k]，其中|j-k|!=1。

来源

蓝桥杯

上一题下一题