m개의 문자와 다른 값 n이 있다고 가정합니다. 우리는 이 m개의 문자에서 문자로 생성된 길이가 n인 문자열의 수를 계산해야 하며 문자열에는 1보다 큰 길이의 회문 부분 문자열이 없습니다. 응답이 너무 크면 결과를 10^9+7로 수정합니다.
따라서 입력이 n =2 m =3과 같으면 m =3이므로 출력은 6이 됩니다. 따라서 알파벳이 {x,y,z}인 경우 [xx,xy,xz]와 같은 문자열을 생성할 수 있습니다. ,yx,yy,yz,zx,zy,zz] 하지만 [xx,yy,zz]는 유효하지 않으므로 6개의 문자열이 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- p :=10^9+7
- n이 1과 같으면
- m 모드 p를 반환
- n이 2와 같으면
- m *(m - 1) 모드 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