C++で最初のN個の階乗の積を10^9+7の剰余で求める方法

問題概要

数値 N が与えられたとき、最初の N 個の階乗の積を 1000000007（10⁹ + 7）で割った余りを求めるのが課題です。

階乗とは、ある整数以下の正の整数すべて（その数自身を含む）の積のことで、「!」（感嘆符）で表されます。例えば、4! = 4 × 3 × 2 × 1 = 24 となります。

つまり、1! から n! まですべて掛け合わせ、その結果を 1000000007 で割った余りを計算することになります。

制約

1 ≤ N ≤ 1e6

入力例 1

n = 9

出力例 1

27

説明： 1! × 2! × 3! × 4! × 5! × 6! × 7! × 8! × 9! を (1e9 + 7) で割った余りは 27 になります。

入力例 2

n = 3

出力例 2

12

説明： 1! × 2! × 3! を (1e9 + 7) で割った余りは 12 になります。

解決のためのアプローチ

• i = 1 から n まで順番に階乗を計算し、それらをすべて掛け合わせます
• 階乗の積を 1e9 + 7 で割った余りを求めます
• 結果を返します

ここで重要なのが mulmod 関数です。大きな数同士の積を直接計算するとオーバーフローの危険があるため、加算と倍化を繰り返す手法（いわゆる「ロシア農民乗算法」の考え方）で (x × y) % mod を安全に求めています。

アルゴリズム

関数 long long int mulmod(long long int x, long long int y, long long int mod)
ステップ1 → result を 0 で宣言・初期化する
ステップ2 → x を x % mod に設定する
ステップ3 → y > 0 の間、以下を繰り返す
　　y % 2 == 1（y が奇数）の場合、
　　　　result を (result + x) % mod に設定する
　　x を (x * 2) % mod に設定する
　　y を y / 2 に設定する
ステップ4 → (result % mod) を返す

関数 long long int nfactprod(long long int num)
　　ステップ1 → product と fact を 1 で宣言・初期化する
　　ステップ2 → MOD を (1e9 + 7) で宣言・初期化する
　　ステップ3 → i = 1 から num まで i を増やしながら繰り返す
　　　　fact を mulmod(fact, i, MOD) の結果に設定する
　　　　product を mulmod(product, fact, MOD) の結果に設定する
　　　　product == 0 の場合、0 を返す
　　ステップ4 → product を返す

関数 int main()
　　ステップ1 → num = 3 で宣言・初期化する
　　ステップ2 → nfactprod(num) を呼び出して結果を出力する
終了

実装例

#include <stdio.h>
long long int mulmod(long long int x, long long int y, long long int mod){
    long long int result = 0;
    x = x % mod;
    while (y > 0) {
        // y が奇数の場合は x を加算する
        if (y % 2 == 1)
            result = (result + x) % mod;
        // x を 2 倍する
        x = (x * 2) % mod;
        // y を 2 で割る
        y /= 2;
    }
    return result % mod;
}
long long int nfactprod(long long int num){
    // product と fact を 1 で初期化する
    long long int product = 1, fact = 1;
    long long int MOD = 1e9 + 7;
    for (int i = 1; i <= num; i++) {
        // 各反復で階乗を求める
        fact = mulmod(fact, i, MOD);
        // 最初の i 個の階乗の積を求める
        product = mulmod(product, fact, MOD);
        // 積が MOD で割り切れる場合は 0 を返す
        if (product == 0)
            return 0;
    }
    return product;
}
int main(){
    long long int num = 3;
    printf("%lld \n", (nfactprod(num)));
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

12

計算量について

mulmod は 1 回の呼び出しごとに y を半分にしながらループするため O(log mod) 時間（約30回程度の反復）かかります。したがって全体の時間計算量は O(N log MOD)、使用メモリは定数 O(1) となります。N が最大 10⁶ でも十分高速に動作します。