nCr ด้วยแฟกทอเรียลที่คำนวณล่วงหน้า

โจทย์จำนวนมากถามว่ามีวิธีเลือกสมาชิก r ตัวจาก n ตัวได้กี่วิธี ซึ่งเขียนเป็น nCr การแข่งขันต้องการคำนวณจำนวนนั้นภายใต้โมดูลัสจำนวนเฉพาะ 🧮

สูตรพื้นฐานคือ nCr เท่ากับ n แฟกทอเรียล หารด้วย r แฟกทอเรียลคูณด้วย n ลบ r แฟกทอเรียล แต่ปัญหาคือการหารภายใต้โมดูลัส

แฟกทอเรียลเพียงตัวเดียวก็มีค่าเพิ่มขึ้นมหาศาล ดังนั้นให้หาเศษของแต่ละค่าด้วย p วิธีนี้ทำให้ทุกค่ามีขนาดเล็ก ขณะที่สูตรยังคงถูกต้องภายใต้โมดูลัส

สร้างอาร์เรย์แฟกทอเรียลไว้ครั้งเดียวจนถึงค่า n มากที่สุดที่ต้องใช้ แต่ละสมาชิกมีค่าเท่ากับสมาชิกก่อนหน้าคูณด้วยดัชนี แล้วหาเศษด้วย p ไปเรื่อย ๆ

สูตรนี้หารด้วยแฟกทอเรียลสองค่า ดังนั้นคุณจึงต้องใช้อินเวอร์สแบบโมดูลัสของทั้งสองค่า โปรดจำไว้ว่าอินเวอร์สจะเปลี่ยนการหารให้เป็นการคูณที่ทำได้อย่างสะอาด

คำนวณอินเวอร์สของแฟกทอเรียลที่มีค่ามากที่สุดเพียงครั้งเดียวด้วยแฟร์มาต์ โดยใช้ pow กับเลขชี้กำลัง p ลบ 2 การเรียกเพียงครั้งเดียวนั้นจะเป็นจุดเริ่มต้นของค่าที่เหลือ

หาอินเวอร์สของแฟกทอเรียลตัวอื่น ๆ ด้วยการวนย้อนกลับเพียงครั้งเดียว โดยแต่ละค่าคำนวณจากค่าถัดไปคูณด้วยดัชนี ไม่ต้องเรียก pow เพิ่ม

ตอนนี้ nCr เป็นเพียง fact[n] คูณด้วย inv_fact[r] คูณด้วย inv_fact[n ลบ r] แล้วหาเศษด้วย p แต่ละคำขอใช้การเข้าถึงข้อมูลสามครั้งและการคูณสองครั้ง

หลังจากคำนวณล่วงหน้าแล้ว คำตอบของการจัดหมู่แต่ละครั้งใช้เวลา O(1) นี่จึงเป็นรูปแบบที่มีประสิทธิภาพมากเมื่อโจทย์ถามค่า nCr หลายพันค่า

หาก r ติดลบหรือมากกว่า n คำตอบคือ 0 ให้ตรวจสอบขอบเขตนี้ก่อน เพื่อไม่ให้เข้าถึงตำแหน่งนอกอาร์เรย์แฟกทอเรียล

กำหนดขนาดอาร์เรย์ให้เท่ากับค่า n สูงสุดจากทุกคำขอ แล้วเผื่อเพิ่มไว้อีกเล็กน้อย ค่าขีดจำกัดที่เล็กเกินไปเป็นสาเหตุทั่วไปของข้อผิดพลาดดัชนีในส่วนนี้

หลังจากคำนวณล่วงหน้าแล้ว คำขอ nCr หนึ่งครั้งใช้เวลาเท่าใด

คุณคำนวณแฟกทอเรียลและอินเวอร์สของแฟกทอเรียลไว้ครั้งเดียว จากนั้นตอบแต่ละ nCr ในเวลา O(1) ด้วยการเข้าถึงข้อมูลสามครั้ง ตรวจสอบขอบเขตของ r และจัดสรรอาร์เรย์ให้มีขนาดเพียงพอ 🏆