计算形成字符串的连续子串的有序的可能不连续的子串的数量

Question

假设 S(N) 是长度为 N 的字符串“012012012...”，其中重复“012”直到我们有 N 个字符。

对于任何给定的 N，通过从字符串中按顺序选择可能不连续的字母来计算形成连续子字符串的方式的数量。

例如，对于 N = 5，我们有 S(N) = "01201"

连续子串和计数：

'0', 2
'1', 2
'2', 1
'01', 3 (the two consecutive '01' along with the first and last character of '01201').
'12', 1
'20', 1
'012', 1
'120', 1
'201', 1
'0120', 1
'1201', 1
'01201', 1

Total: 16

对于任意 N，我们如何有效地计算它？我会 post 我的最佳答案作为解决方案。

注意这个问题最初来自Cococino223，但是措辞不当，没来得及修复就被删除了。

Answer 1

假设 f(n) 是 n 的计数，f(n, k) 是在 {0,1,2} 中以 k 结尾的那些子字符串的 n 的计数。

N  f(n, 0)  f(n, 1)  f(n, 2)  f(n)
0       0        0        0     0      
1       1        0        0     1      
2       1        2        0     3      
3       1        2        3     6      
4       5        2        3    10       
5       5        8        3    16       
6       5        8       12    25        
7      18        8       12    38        
8      18       27       12    57          
9      18       27       40    85          
10     59       27       40    126           
11     59       87       40    186

方法：f(n, k) 仅在第 n 个字符串以 k 结尾时才会改变。在那种情况下：

f(n, k) = f(n-1, k) + f(n-1, k') + 1
Where k' is the predecessor of k in '012' with wraparound.

E.g., f(6,2) = 12 = f(5,2) + f(5,1) + 1

这里的直觉是我们有所有不使用最新字母 (f(n-1, k)) 以 k 结尾的方法，所有使用最新 k 的方法，必须等于所有使用序列中前一个字母的方法，最后添加 k (f(n-1, k'))，连同单例新 k (+1).

这是线性时间，常量记忆。

-- update -- 如果你读到变化的数字：1, 2, 3, 5, 8, 12, 18, 27, 40, 59, 87, 128, 188, 276, 405, 594, 871，这里是OEIS sequence A077868.

-- 更新--

[a, b, c, 1] * [0, 0, 1, 0] = [b, c, a+c+1, 1]
               [1, 0, 0, 0]
               [0, 1, 1, 0]
               [0, 0, 1, 1]

调用M上面的方阵，然后我们就可以用M来计算k的连续值了。例如，[12, 18, 27, 1] * M = [18, 27, 40, 1]

我们可以使用它通过重复对矩阵求平方来在对数时间内求解 f(n)。

E.g. M^8 = [4,   6,  9, 0]
           [3,   4,  6, 0]
           [6,   9, 13, 0]
           [12, 18, 27, 1]

[0, 0, 0, 1] * M^8 = [12, 18, 27, 1]
12 + 18 + 27 = 57 = f(8)

f(n)是M^n底行前三个元素之和

所以 f(n) 可以用对数时间计算，但是因为矩阵 mult 相当昂贵，所以这只对相对较大的 n 有意义。请注意，这适用于不是 2 的幂的数字，方法是将 2 的适当幂的矩阵相乘。例如13 = 1101，所以我们乘以 (M^1)(M^4)(M^8).

计算形成字符串的连续子串的有序的可能不连续的子串的数量

Counting the number of ordered possibly nonconsecutive substrings that form consecutive substrings of a string

algorithm

dynamic-programming