크기가 n이고 nums[i]가 공 i의 수를 나타내는 배열 nums로 번호가 매겨진 n개의 공이 있다고 가정합니다. 이제 다른 값 k가 있습니다. 각 턴에서 우리는 n개의 다른 공에서 k개의 공을 선택하고 k개의 공의 최대값과 최소값의 차이를 찾고 그 차이를 테이블에 저장합니다. 그런 다음 이 k개의 공을 다시 그 냄비에 넣고 가능한 모든 선택 항목을 선택할 때까지 다시 선택합니다. 마지막으로 표에서 모든 차이의 합계를 찾으십시오. 답이 너무 크면 결과 모드 10^9+7을 반환합니다.
따라서 입력이 n =4 k =3 nums =[5, 7, 9, 11]과 같으면 조합이 -
이기 때문에 출력은 20이 됩니다.- [5,7,9], 차이 9-5 =4
- [5,7,11], 차이 11-5 =6
- [5,9,11], 차이 11-5 =6
- [7,9,11], 차이 11-7 =4
따라서 4+6+6+4 =20입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- m :=10^9 + 7
- inv :=[0, 1] 요소가 있는 새 목록
- 2~n 범위의 i에 대해 다음을 수행합니다.
- inv 끝에 (m - floor of (m / i) * inv[m mod i] mod m) 삽입
- comb_count :=1
- res :=0
- k - 1 ~ n - 1 범위에서 선택하려면
- res :=res +(nums[pick] - nums[n - 1 - pick]) * comb_count mod m
- res :=res 모드 m
- comb_count :=comb_count *(pick + 1) mod m * inv[pick + 2 - k] mod m
- 반환 결과
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n, k, nums): m = 10**9 + 7 inv = [0, 1] for i in range(2, n + 1): inv.append(m - m // i * inv[m % i] % m) comb_count = 1 res = 0 for pick in range(k - 1, n): res += (nums[pick] - nums[n - 1 - pick]) * comb_count % m res %= m comb_count = comb_count * (pick + 1) % m * inv[pick + 2 - k] % m return res n = 4 k = 3 nums = [5, 7, 9, 11] print(solve(n, k, nums))
입력
4, 3, [5, 7, 9, 11]
출력
20