有效序列数

Question

如果序列以1开头并以给定数字

j结束，并且没有两个相邻的数字相同，则n个序列[[n]被视为有效。序列可以使用1到给定数k之间的任何整数（包括1和<1>。<= j <= k）。给定参数n，j，k，计算有效序列的数量。有效序列的数量可能非常大，因此请以10 10 + 7为模表示您的答案。^{我正在尝试找到此问题的线性时间解决方案。这是几年前一位朋友参加的比赛。}

例如

1）n = 4，k = 4，j = 2。

2）n = 10

7

，k = 10 ¹²，j = 829。^{如果序列以1开头，以给定的数字j结束，并且没有两个相邻的数字相同，则n个数字的序列被视为有效。序列可以使用1到给定之间的任何整数...}

Answer 1

我将概述其中的所有内容，以帮助您继续前进。但是会剩下大部分工作。