สมมติว่าเรามีลูกบอล n ลูกซึ่งมีหมายเลขเป็นอาร์เรย์ nums ซึ่งมีขนาด n และ nums[i] แทนจำนวนลูก i ตอนนี้เรามีค่า k อีกค่าหนึ่ง ในแต่ละเทิร์น เราเลือก k ลูกจาก n ลูกที่แตกต่างกัน และค้นหาความแตกต่างของค่าสูงสุดและต่ำสุดของ k ball และเก็บความแตกต่างไว้ในตาราง จากนั้นใส่ k ลูกเหล่านี้ลงในหม้อนั้นอีกครั้งและเลือกอีกครั้งจนกว่าเราจะเลือกตัวเลือกที่เป็นไปได้ทั้งหมด ในที่สุดก็หาผลรวมของความแตกต่างทั้งหมดจากตาราง หากคำตอบมีขนาดใหญ่เกินไป ให้คืนค่า mod ผลลัพธ์ 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
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ม :=10^9 + 7
- inv :=รายการใหม่พร้อมองค์ประกอบ [0, 1]
- สำหรับฉันในช่วง 2 ถึง n ทำ
- แทรก (m - ชั้นของ (m / i) * inv[m mod i] mod m) ที่ส่วนท้ายของ inv
- comb_count :=1
- res :=0
- สำหรับการเลือกในช่วง k - 1 ถึง n - 1 ทำ
- res :=res +(nums[pick] - nums[n - 1 - pick]) * comb_count mod m
- res :=res mod 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
