将串分成四类： 1. 没有3连 + 末尾两个数字不同， A[L] 2. 没有3连 + 末尾两个数字相同， B[L] 3. 恰有1个3连 + 末尾两个数字不同， C[L] 4. 恰有1个3连 + 末尾两个数字相同， D[L] 有如下递推关系： A[2] = S * (S - 1) B[2] = S C[2] = 0 D[2] = 0 令R = S - 1以方便书写 A[L+1] = A[L] * R + B[L] * R B[L+1] = A[L] C[L+1] = C[L] * R + D[L] * R D[L+1] = B[L] + C[L] 最后输出结果C[L] + D[L]之和即可。 时间复杂度为O(L)