Repository: TheAlgorithms/C-Plus-Plus
File: math/ncr_modulo_p.cpp (C++)

Code before:
    }

    int64_t x1 = 0, y1 = 0;
    const int64_t gcd = gcdExtended(b % a, a, x1, y1);

    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

/** Find modular inverse of a modulo m i.e. a number x such that (a*x)%m = 1
 *
 * @param[in] a the number for which the modular inverse is queried
 * @param[in] m the modulus
 * @return the inverce of a modulo m, if it exists, -1 otherwise
 */
int64_t modInverse(const int64_t& a, const int64_t& m) {
    int64_t x = 0, y = 0;
    const int64_t g = gcdExtended(a, m, x, y);
    if (g != 1) {  // modular inverse doesn't exist
        return -1;
    } else {
        return ((x + m) % m);
    }
}
};  // namespace utils
/**
 * @brief Class which contains all methods required for calculating nCr mod p
 */
class NCRModuloP {
 private:
    const int64_t p;  /// the p from (nCr % p)
    const std::vector<int64_t>
        fac;  /// stores precomputed factorial(i) % p value

    /**
     * @brief computes the array of values of factorials reduced modulo mod
     * @param max_arg_val argument of the last factorial stored in the result
     * @param mod value of the divisor used to reduce factorials
     * @return vector storing factorials of the numbers 0, ..., max_arg_val
     * reduced modulo mod
     */
    static std::vector<int64_t> computeFactorialsMod(const int64_t& max_arg_val,
                                                     const int64_t& mod) {
        auto res = std::vector<int64_t>(max_arg_val + 1);
        res[0] = 1;
        for (int64_t i = 1; i <= max_arg_val; i++) {
            res[i] = (res[i - 1] * i) % mod;
        }
        return res;
    }

Review comment (suggestion):
AFAIK, namespaces don't use `;` at the end of them.
```suggestion
}  // namespace utils
```


Code after:
    }

    int64_t x1 = 0, y1 = 0;
    const int64_t gcd = gcdExtended(b % a, a, x1, y1);

    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

/** Find modular inverse of a modulo m i.e. a number x such that (a*x)%m = 1
 *
 * @param[in] a the number for which the modular inverse is queried
 * @param[in] m the modulus
 * @return the inverce of a modulo m, if it exists, -1 otherwise
 */
int64_t modInverse(const int64_t& a, const int64_t& m) {
    int64_t x = 0, y = 0;
    const int64_t g = gcdExtended(a, m, x, y);
    if (g != 1) {  // modular inverse doesn't exist
        return -1;
    } else {
        return ((x + m) % m);
    }
}
}  // namespace utils
/**
 * @brief Class which contains all methods required for calculating nCr mod p
 */
class NCRModuloP {
 private:
    const int64_t p = 0;  /// the p from (nCr % p)
    const std::vector<int64_t>
        fac;  /// stores precomputed factorial(i) % p value

    /**
     * @brief computes the array of values of factorials reduced modulo mod
     * @param max_arg_val argument of the last factorial stored in the result
     * @param mod value of the divisor used to reduce factorials
     * @return vector storing factorials of the numbers 0, ..., max_arg_val
     * reduced modulo mod
     */
    static std::vector<int64_t> computeFactorialsMod(const int64_t& max_arg_val,
                                                     const int64_t& mod) {
        auto res = std::vector<int64_t>(max_arg_val + 1);
        res[0] = 1;
        for (int64_t i = 1; i <= max_arg_val; i++) {
            res[i] = (res[i - 1] * i) % mod;
        }
        return res;
    }