C++-তে প্রথম N ফ্যাক্টোরিয়ালের গুণফল বের করা (মডুলো 1e9+7)

একটি সংখ্যা N দেওয়া আছে। প্রথম Nটি ফ্যাক্টোরিয়ালের গুণফল মডুলো ১০০০০০০০০৭ (1e9+7) বের করতে হবে। ফ্যাক্টোরিয়াল মানে ১ থেকে সেই সংখ্যা পর্যন্ত গুণফল (যেমন ৪! = ৪×৩×২×১ = ২৪)।

কনস্ট্রেইন্ট − ১ ≤ N ≤ ১০⁶

ইনপুট − n = 9

আউটপুট − 27 (উদাহরণে দেওয়া আউটপুট ২৭, কিন্তু আসলে ৯! পর্যন্ত গুণফল মডুলো ১e9+7 হবে অন্য মান। নিচের কোডে সঠিক ক্যালকুলেশন আছে।)

ইনপুট − n = 3

আউটপুট − 12

ব্যাখ্যা − ১! × ২! × ৩! = ১ × ২ × ৬ = ১২

প্রোগ্রামে ব্যবহৃত পদ্ধতি

রিকার্শিভ বা ইটারেটিভ ফ্যাক্টোরিয়াল ক্যালকুলেট করুন।
প্রতিটি ফ্যাক্টোরিয়ালকে রানিং প্রোডাক্ট দিয়ে গুণ করুন।
প্রতিটি গুণফলে মডুলো ১e9+7 নিন।
ওভারফ্লো এড়াতে mulmod ফাংশন ব্যবহার করুন (রাশিয়ান পিজ্যান্ট মাল্টিপ্লিকেশন)।

অ্যালগরিদম

Function mulmod(x, y, mod)
  result = 0
  x = x % mod
  while y > 0
    if y%2 == 1: result = (result + x) % mod
    x = (x * 2) % mod
    y = y / 2
  return result % mod

Function nfactprod(num)
  product = 1, fact = 1
  MOD = 1e9+7
  for i = 1 to num
    fact = mulmod(fact, i, MOD)
    product = mulmod(product, fact, MOD)
    if product == 0: return 0
  return product

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

long long mulmod(long long x, long long y, long long mod) {
    long long result = 0;
    x %= mod;
    while (y > 0) {
        if (y % 2 == 1)
            result = (result + x) % mod;
        x = (x * 2) % mod;
        y /= 2;
    }
    return result % mod;
}

long long nfactprod(long long num) {
    long long product = 1, fact = 1;
    long long MOD = 1000000007;
    for (int i = 1; i <= num; i++) {
        fact = mulmod(fact, i, MOD);
        product = mulmod(product, fact, MOD);
        if (product == 0) return 0;
    }
    return product;
}

int main() {
    long long num = 3;
    cout << nfactprod(num) << endl;
    return 0;
}