สมมติว่าเรามีตัวอักษรจำนวน m และค่าอื่น n เราต้องนับจำนวนสตริงที่มีความยาว n ที่สร้างด้วยตัวอักษรโดยใช้ตัวอักษร m เหล่านี้ และ string ไม่มีสตริงย่อย palindromic ที่มีความยาวมากกว่า 1 หากคำตอบใหญ่เกินไป ให้แก้ไขผลลัพธ์ด้วย 10^9+7
ดังนั้น หากอินพุตเป็น n =2 m =3 ผลลัพธ์จะเป็น 6 เนื่องจาก m =3 ดังนั้นหากตัวอักษรเป็น {x,y,z} เราสามารถสร้างสตริงเช่น [xx,xy,xz ,yx,yy,yz,zx,zy,zz] แต่ [xx,yy,zz] ไม่ถูกต้อง ดังนั้นจึงมี 6 สตริง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- p :=10^9+7
- ถ้า n เหมือนกับ 1 แล้ว
- คืนค่า m mod p
- ถ้า n เหมือนกับ 2 แล้ว
- คืนค่า m *(m - 1) mod p
- ถ้า m <=2 แล้ว
- คืน 0
- คืนค่า m*(m-1) * ((m-2)^(n-2) mod p) mod p
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
3, [1,2,3,4,1]
ผลลัพธ์
6
