โปรแกรมนับสตริงความยาว n จากอักษร m ตัวโดยไม่มีพาลินโดรมยาวกว่า 1 ใน Python

สมมติว่ามีอักษร m ตัว และค่า n เราต้องนับจำนวนสตริงความยาว n ที่สร้างจากอักษร m ตัวนี้ โดยที่สตริงไม่มีส่วนย่อยที่เป็นพาลินโดรมยาวกว่า 1 หากคำตอบใหญ่เกินไป ให้คืนค่าตามโมดูล로 10^9+7

ตัวอย่าง: n = 2, m = 3 ผลลัพธ์คือ 6 เพราะอักษรคือ {x,y,z} สตริงที่เป็นไปได้คือ [xx,xy,xz,yx,yy,yz,zx,zy,zz] แต่ [xx,yy,zz] เป็นพาลินโดรม จึงเหลือ 6 สตริง

ขั้นตอนการแก้ปัญหา

1. กำหนด p = 10^9+7
2. หาก n = 1 คืนค่า m % p
3. หาก n = 2 คืนค่า m * (m - 1) % p
4. หาก m <= 2 คืนค่า 0 (เพราะไม่สามารถสร้างสตริงโดยไม่มีพาลินโดรมได้)
5. กรณีทั่วไป: คืนค่า m * (m - 1) * pow(m - 2, n - 2, p) % p

ตัวอย่างโค้ด 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))  # ผลลัพธ์: 6

อินพุตตัวอย่าง

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

เอาต์พุตตัวอย่าง

6