统计012周期字符串S(N)的有序选取匹配连续子串的总计数及高效算法

定义字符串S(N)为重复拼接固定序列"012"直至凑够N个字符生成的循环串，形式为012012012...。
针对任意给定的正整数N，需计算满足以下条件的选取方式总数量：

• 从S(N)中按字符出现的先后顺序选取（允许选取不相邻的字符，仅要求相对顺序和原串一致）
• 最终选出的字符序列，恰好等于S(N)本身的某一个连续子串

参考示例（N=5） #

此时S(5) = "01201"，逐一枚举所有连续子串对应的合法选取次数，结果如下：

子串对应的合法计数：
'0'：2
'1'：2
'2'：1
'01'：3
（注：包含两处相邻的"01"实例的直接选取，以及取串首'0'、串末'1'的非连续选取）
'12'：1
'20'：1
'012'：1
'120'：1
'201'：1
'0120'：1
'1201'：1
'01201'：1

所有子串计数累加，总结果为16

求解目标 #

推导适用于任意N的高效计算方法，避免逐一枚举所有子串、逐一遍历所有选取组合的低效实现，实现极低时间复杂度的通用求解。

说明：本题最初由用户Cococino223提出，原表述不够完善被删除后，本次整理为正式技术问询。

内容的提问来源于stack exchange，提问作者Dave