Prefix Product Construction — முன்னொட்டு பெருக்கல் கட்டுமானம்

Prefix product — prefix sum போல் பெருக்கல்; modular கோட்பாடு, சுயாதீன நிகழ்தகவு, “தன்னைத் தவிர்த்து பெருக்கல்” வினாக்களில் — பூஜ்ஜியம் கவனம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

வளர்ச்சி காரணிகள் — காலங்களைப் பெருக்கி மொத்த விரிவு; முதல் k படிகள் வினா. நம்பகத்தன்மை சங்கிலி — உயிர்வாழ் நிகழ்தகவு பெருக்கல். போட்டியில் modulo; பகு எண் prime மற்றும் இணை முதலீடு போது inverse.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

p[k] என்பது a[0..k] பெருக்கல்; தொடக்கம் 1. MOD எனில் ஒவ்வொரு பெருக்கலிலும் mod. பூஜ்ஜியம் — பிரிவு அல்லது கடைசி பூஜ்ஜிய index. “a[i] நீக்கி பெருக்கல்” — prefix + suffix O(n).

Pythonில் முயற்சி செய்வோம்

MOD = 1_000_000_007


def prefix_products(a: list[int]) -> list[int]:
    p = 1
    out = []
    for x in a:
        p = p * x % MOD
        out.append(p)
    return out


print(prefix_products([2, 3, 4]))

அடிக்கடி நேரும் தவறுகள்

• முதலீடு MOD உடன் பொதுவகு இருக்கும்போது Fermat inverse.
• mod முன் வெடிப்பு.
• factorial போன்ற பிரச்சினைகளில் காரணி எண்ணிக்கை.

முக்கியச் சுருக்கக் குறிப்புகள்

• prefix+suffix — பல offline பெருக்கல் வினாக்கள்.
• mod, பூஜ்ஜியம், எதிர் தெளிவு.
• log-domain — நேர்ம அடிப்படை மட்டும்.