Ajob 언어라는 이상한 언어가 있다고 가정합니다. 글자 수는 무한합니다. 우리는 이 언어로 n개의 단어를 알고 있습니다. 첫 번째 단어는 1자 길이이고, 두 번째 단어는 2자 길이입니다. 그리고 단어의 모든 글자는 고유합니다. n 단어 중 하나를 선택하고 그로부터 하위 시퀀스를 형성하는 경우. 하위 시퀀스의 길이는 원래 단어의 길이보다 k 작아야 합니다. 예를 들어 선택한 단어의 길이가 L이라고 하면 하위 시퀀스의 길이는 (L - k)여야 합니다. 길이가 k보다 작은 단어가 있으면 해당 단어를 선택해서는 안 됩니다. 그리고 두 부분 시퀀스의 길이가 다르거나 같은 위치에 다른 문자가 포함되어 있으면 두 부분 시퀀스가 서로 다릅니다. 우리는 결과 모듈로 p와 p i 소수를 찾아야 합니다.
따라서 입력이 n =6, k =5, p =11과 같으면 출력은 7이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 빈 사전 메모 하나 만들기
- n :=n + 1, k :=k + 1
- fact :=하나의 요소가 있는 목록 1
- 1~p-1 범위의 i에 대해 다음을 수행합니다.
- 팩트의 끝에 (팩트의 마지막 요소 * i mod p) 삽입
- p가 메모에 있으면
- inv_fact :=메모[p]
- 그렇지 않으면
- inv :=0과 1의 두 요소가 있는 목록
- 2~p-1 범위의 i에 대해 다음을 수행합니다.
- inv 끝에 (p - p/i의 바닥 * inv[p mod i] mod p) 삽입
- inv_fact :=하나의 요소가 있는 목록 1
- 1~p-1 범위의 i에 대해 다음을 수행합니다.
- inv_fact 끝에 삽입(inv_fact * inv[i] mod p의 마지막 요소)
- 메모[p] :=inv_fact
- ret :=1
- n> 0일 때 수행
- n1 :=n 모드 p
- k1 :=k 모드 p
- k1> n1이면
- 0을 반환
- ret :=ret * 사실[n1] * inv_fact[k1] * inv_fact[n1 - k1] 모드 p
- n :=(n/p)의 바닥
- k :=k/p의 바닥
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
memo = {}
def solve(n, k, p):
n += 1
k += 1
fact = [1]
for i in range(1, p):
fact.append(fact[-1] * i % p)
if p in memo:
inv_fact = memo[p]
else:
inv = [0, 1]
for i in range(2, p):
inv.append(p - p // i * inv[p % i] % p)
inv_fact = [1]
for i in range(1, p):
inv_fact.append(inv_fact[-1] * inv[i] % p)
memo[p] = inv_fact
ret = 1
while n > 0:
n1 = n % p
k1 = k % p
if k1 > n1:
return 0
ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
n //= p
k //= p
return ret
n = 6
k = 5
p = 11
print(solve(n, k, p)) 입력
6, 5, 11
출력
7