Chương trình tìm chuỗi độ dài n được tạo từ các chữ cái từ bảng chữ cái có kích thước m không có palindrome bằng Python

Giả sử chúng ta có m số chữ cái và một giá trị n khác. Chúng ta phải đếm số chuỗi có độ dài n được tạo bằng các chữ cái bằng cách lấy từ m chữ cái này và chuỗi không có chuỗi con palindromic có độ dài lớn hơn 1. Nếu câu trả lời quá lớn thì hãy sửa đổi kết quả bằng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =2 m =3, thì đầu ra sẽ là 6 vì m =3, vì vậy nếu các bảng chữ cái là {x, y, z}, chúng ta có thể tạo ra các chuỗi như:[xx, xy, xz , yx, yy, yz, zx, zy, zz] nhưng [xx, yy, zz] không hợp lệ nên có 6 chuỗi.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• p:=10 ^ 9 + 7
• nếu n giống 1, thì
  • trả lại m mod p
• nếu n giống 2 thì
  • return m * (m - 1) mod p
• nếu m <=2, thì
  • trả về 0
• trả về m * (m-1) * ((m-2) ^ (n-2) mod p) mod p

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

3, [1,2,3,4,1]

Đầu ra

6