Đếm chuỗi độ dài n từ bảng chữ cái m ký tự không chứa xâu đối xứng trong Python

Cho m ký tự và một số n. Cần đếm số chuỗi độ dài n tạo từ m ký tự sao cho chuỗi không chứa bất kỳ xâu con đối xứng (palindrome) nào có độ dài lớn hơn 1. Kết quả lấy modulo 10^9+7 nếu quá lớn.

Ví dụ: n = 2, m = 3. Các chuỗi có thể: [xx, xy, xz, yx, yy, yz, zx, zy, zz]. Loại bỏ [xx, yy, zz] (đối xứng độ dài 2) còn 6 chuỗi hợp lệ.

Giải thuật

• p = 10^9+7.
• Nếu n == 1: trả về m % p.
• Nếu n == 2: trả về m * (m - 1) % p.
• Nếu m ≤ 2: trả về 0 (không thể tạo chuỗi thỏa mãn).
• Trả về m * (m - 1) * ((m - 2)^(n - 2) mod p) mod p.

Ví dụ mã Python

def solve(n, m):
    p = 10**9 + 7
    if n == 1:
        return m % p
    if n == 2:
        return m * (m - 1) % p
    if m <= 2:
        return 0
    return m * (m - 1) * pow(m - 2, n - 2, p) % p

n = 2
m = 3
print(solve(n, m))  # Output: 6

Đầu vào

2, 3

Đầu ra

6