1에서 n까지의 순열 수를 찾아야 하므로 소수는 소수 인덱스에 배치됩니다. 답이 클 수 있습니다. 모듈로 10^9 + 7을 반환합니다. 따라서 n =5이면 출력은 12가 됩니다. 따라서 12개의 순열이 있습니다. 하나의 가능한 순열은 [1,2,5,4,3]이고 하나의 잘못된 순열은 [5,2,3,4,1]입니다. 5가 소수가 아닌 인덱스 1에 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- getNum이라는 메소드를 다음과 같이 정의하십시오. -
- prime :=2에서 100까지의 모든 소수 목록
- 세트 i :=0
- while i <프라임 리스트의 길이
- prime[i]> n이면 i를 반환합니다.
- 나는 :=나는 + 1
- 소수의 반환 길이
- 실제 문제는 다음과 같이 해결됩니다.
- x :=getNum(n), p :=1, m :=10^9 + 7
- i:=x에서 0까지
- p :=p * 나는
- p :=p 모드 m
- i:=n – x에서 0까지
- p :=p * 나는
- p :=p 모드 m
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def getNum(self,n): primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] i = 0 while i < len(primes): if primes[i]>n: return i i+=1 return len(primes) def numPrimeArrangements(self, n): """ :type n: int :rtype: int """ x = self.getNum(n) p = 1 m = 1000000000+7 for i in range(x,0,-1): p*=i p%=m for i in range(n-x,0,-1): p*=i p%=m return p ob1 = Solution() print(ob1.numPrimeArrangements(100))
입력
100
출력
682289015