‏nCr باستخدام المضروبات المحسوبة مسبقًا

تسأل العديد من المسائل عن عدد طرق اختيار r عنصرًا من n، ويُكتب ذلك nCr. وتطلب مسابقات البرمجة حساب هذا العدد تحت modulus أولي. 🧮

الصيغة الكلاسيكية هي أن nCr يساوي مضروب n مقسومًا على حاصل ضرب مضروب r ومضروب n ناقص r. لكن المشكلة هي القسمة تحت modulo.

ينمو المضروب الواحد نموًا فلكيًا، لذا احسب modulo p لكل مضروب. يحافظ ذلك على صغر كل قيمة مع بقاء الصيغة دقيقة تحت modulus.

أنشئ مصفوفة fact مرة واحدة حتى أكبر قيمة n تحتاج إليها. يساوي كل عنصر العنصر السابق مضروبًا في الفهرس، مع حساب modulo p في كل خطوة.

تقسم الصيغة على مضروبين، لذا تحتاج إلى معكوسَي modulo لهما. تذكّر أن المعكوس يحوّل القسمة إلى ضرب مباشر.

احسب معكوس أكبر مضروب مرة واحدة باستخدام Fermat، وذلك باستعمال pow مع الأس p ناقص 2. يهيئ ذلك الاستدعاء الواحد بقية القيم.

احصل على معكوسات المضروب الأخرى في مرور واحد إلى الخلف، بحيث يُحسب كل منها من العنصر التالي مضروبًا في الفهرس. ولا تحتاج إلى استدعاءات pow إضافية.

أصبح nCr الآن مجرد fact[n] مضروبًا في inv_fact[r] ومضروبًا في inv_fact[n minus r]، مع حساب modulo p للجميع. ثلاث عمليات وصول وعملية ضرب لكل استعلام.

بعد الحساب المسبق، تصبح إجابة كل توافق في O(1). ولهذا تتألق هذه الطريقة عندما تطلب المسألة آلاف القيم من nCr.

إذا كان r سالبًا أو أكبر من n، فالإجابة هي 0. افحص هذا الشرط أولًا حتى لا تصل إلى موضع خارج مصفوفات المضروب.

اجعل حجم المصفوفة مساويًا لأكبر n بين جميع الاستعلامات مع إضافة هامش صغير. يمثل limit الأصغر من اللازم سببًا شائعًا لأخطاء الفهارس هنا.

بعد الحساب المسبق، ما سرعة استعلام nCr واحد؟

تحسب مسبقًا المضروبات ومعكوساتها مرة واحدة، ثم تجيب عن كل nCr في O(1) باستخدام ثلاث عمليات وصول. تحقّق من حدود r واجعل المصفوفات كبيرة بما يكفي. 🏆