有效序列数
Number of valid sequences
一个 n 个数字的序列如果以 1 开头，以给定的数字 j 结束，并且没有两个则被认为是有效的相邻的数字相同。序列可以使用 1 和给定数字 k 之间的任何整数，包括（也包括 1 <= j <= k).给定参数n,j,k,统计有效序列的个数。有效序列的数量可能非常大，因此请将您的答案取模 1010 + 7.
我正在尝试找到解决此问题的线性时间解决方案。这是几年前一个朋友参加的比赛。
例如
1) n = 4, k = 4, j = 2.
2) n = 107, k = 1012, j = 829.
我会列出足够多的内容来帮助你继续。但是会把大部分工作留给你。
请注意，由于对称性，在任何圈数之后，在任何特定非 1 值处结束的方式数与在任何其他值处结束的方式相同。因此，如果 x_m_l 是构建到目前为止有效序列的方法数，该序列在 m 步结束于 l，则 x_m_2 == x_m_3 == ... == x_m_k。但是 x_m_1 可能不一样。所以让我们调用 x_m_1 x_m 和其他 y_m.
我们立即得到 x_0 = 1 和 y_0 = 0。经过一番思考，我们有 x_(m+1) = (k-1) * y_m。还有 y_(m+1) = x_m + (k-2) * y_m.
将其写为矢量（请原谅糟糕的 ASCII 艺术）第一个是：
( x_0 ) -- ( 1 )
( y_0 ) -- ( 0 )
而第二个变成如下矩阵方程：
( x_(m+1) ) -- [ 0 k-1 ] ( x_m )
( y_(m+1) ) -- [ 1 k-2 ] ( y_m )
到目前为止一切顺利。但是我们称该转换矩阵为 T。它使我们向前迈进了一步。但是如果你想向前移动2步，你可以乘以T两次。 T^2。只需 3 个步骤 T^3。等等。
结果是T^m是向前移动m步的矩阵。 T^n 包含您的答案。 （您是否查看向量中的第一个或第二个条目取决于是 j=1 还是其他。）
如果您只是通过重复乘法（进行模运算）来计算 T^n，您将得到想要的答案。
如果你对重复平方很聪明，你实际上可以在对数时间内解决它。
一个 n 个数字的序列如果以 1 开头，以给定的数字 j 结束，并且没有两个则被认为是有效的相邻的数字相同。序列可以使用 1 和给定数字 k 之间的任何整数，包括（也包括 1 <= j <= k).给定参数n,j,k,统计有效序列的个数。有效序列的数量可能非常大，因此请将您的答案取模 1010 + 7.
我正在尝试找到解决此问题的线性时间解决方案。这是几年前一个朋友参加的比赛。
例如
1) n = 4, k = 4, j = 2.
2) n = 107, k = 1012, j = 829.
我会列出足够多的内容来帮助你继续。但是会把大部分工作留给你。
请注意，由于对称性，在任何圈数之后，在任何特定非 1 值处结束的方式数与在任何其他值处结束的方式相同。因此，如果 x_m_l 是构建到目前为止有效序列的方法数，该序列在 m 步结束于 l，则 x_m_2 == x_m_3 == ... == x_m_k。但是 x_m_1 可能不一样。所以让我们调用 x_m_1 x_m 和其他 y_m.
我们立即得到 x_0 = 1 和 y_0 = 0。经过一番思考，我们有 x_(m+1) = (k-1) * y_m。还有 y_(m+1) = x_m + (k-2) * y_m.
将其写为矢量（请原谅糟糕的 ASCII 艺术）第一个是：
( x_0 ) -- ( 1 )
( y_0 ) -- ( 0 )
而第二个变成如下矩阵方程：
( x_(m+1) ) -- [ 0 k-1 ] ( x_m )
( y_(m+1) ) -- [ 1 k-2 ] ( y_m )
到目前为止一切顺利。但是我们称该转换矩阵为 T。它使我们向前迈进了一步。但是如果你想向前移动2步，你可以乘以T两次。 T^2。只需 3 个步骤 T^3。等等。
结果是T^m是向前移动m步的矩阵。 T^n 包含您的答案。 （您是否查看向量中的第一个或第二个条目取决于是 j=1 还是其他。）
如果您只是通过重复乘法（进行模运算）来计算 T^n，您将得到想要的答案。
如果你对重复平方很聪明，你实际上可以在对数时间内解决它。