386小C的合法k-size字符串问题

问题描述

小 C 最近在研究合法的 k-size 字符串。一个字符串被称为 k-size，是指它可以被分成恰好 k 段连续的相同字符组成的子串。

例如：

• 字符串 “aabbbccc” 是 3-size，因为它可以分成 [“aa”, “bbb”, “ccc”] 这三段。
• 字符串 “ababaab” 是 6-size，因为它可以分成 [“a”, “b”, “a”, “b”, “aa”, “b”] 这六段。

小 C 认为，只有当每个连续段的长度至少为 2 时，该字符串才是合法的。例如，”aabbbccc” 是合法的，而 “ababaab” 不是合法的。

现在，给定字符串长度 n 和要求的连续段数量 k，小 C 想知道，长度为 n 的、仅由小写字母组成的合法的 k-size 字符串有多少个？答案可能非常大，请将结果对 10^9+7 取模。

解题思路

1. 分段计数
   将字符串分成 k 段，每段由相同字符组成，且每段长度至少为 2。设每段的长度为 L₁, L₂, …, Lₖ，则有
     L₁ + L₂ + … + Lₖ = n，并且 Lᵢ ≥ 2。
   令 xᵢ = Lᵢ - 2（xᵢ ≥ 0），则
     x₁ + x₂ + … + xₖ = n - 2k。
   非负整数解的个数即为
     C((n - 2k) + k - 1, k - 1) = C(n - k - 1, k - 1)。

2. 选字母方案
   每一段所用的字符均相同，且相邻段的字符不同。

   • 第一段有 26 种选法
   • 剩余每段必须和前一段不同，因此每段有 25 种选法
     故字母的选取方案为 26 × 25^(k - 1)。

3. 最终答案
   合法的 k-size 字符串数为两部分组合，即
      答案 = C(n - k - 1, k - 1) × 26 × 25^(k - 1)。
   由于 n 和 k 可能较大，计算过程中需要使用模 1e9+7。

实现代码

def C(n, m, p):
    if m < 0 or n < m:
        return 0
    if m == 0:
        return 1
    m = min(m, n - m)
    a = 1
    b = 1
    for i in range(1, m + 1):
        a = a * (n - i + 1) % p
        b = (b * i) % p
    return a * pow(b, p - 2, p) % p

def lucas(n, m, p):
    return C(n % p, m % p, p) * lucas(n // p, m // p, p) % p if m else 1

mod = int(1e9 + 7)
def solution(n: int, k:int) -> int:
    return lucas(n - k - 1, k - 1, mod) * 26 * pow(25, k - 1, mod) % mod

if __name__ == '__main__':
    print(solution(n = 2, k = 1) == 26)
    print(solution(n = 4, k = 2) == 650)
    print(solution(n = 10, k = 5) == 10156250)

复杂度分析

时间复杂度：$O(k)$。
空间复杂度：$O(1)$。