Как найти факториалы больших чисел по модулю 1000000007 в C++?

Question

Найти факториал большого числа по модулю 1000000007

В Python или Java, это не проблема, но в C++ есть переполнение ограничений.

Это код, который я пробовал:

#include<iostream> 
#define ull long long int 
#define mod 1000000007 
ull fact(ull n) 
{ 
      if(n==1 || n==0) return 1; 
      return ((n%mod)*(fact(n-1)%mod)%mod); 
} 
int main() 
{ 
       cout<<fact(50000)<<endl; 
       return 0; 
} 

Но выход недействителен.

Answer 1

этот код. Не должно быть никаких проблем, так как unsigned long long может легко хранить любое модульное значение 10^9 + 7. Я имею в виду, если вы используете модульное значение вместо фактического, то зачем вам это вообще нужно? (Известно, что 10^9 + 7 может храниться в ull).

ull ans; 
    ull fact(int n) 
    { 
     if(n<INT_MAX) 
     { 
     ans=1; 
     for(int i=2;i<=n;i++) 
     ans=(ans*i)%mod; 
     return ans; 
     } 
    } 

Это просто сделает факториал.

Здесь п < INT_MAX условие используется, потому что если мы не будем использовать его тогда, если п = INT_MAX для индекса прироста передачи контура в (я ++) может привести к inceasing значение INT_MAX, который будет делать это 0. Таким образом, условие будет никогда не будет ложным, и он будет запущен в бесконечный цикл.

Примечание: Если вы хотите точно рассчитать факториал в C++, вы можете взять массив из 1000 символов, где каждый из символов представляет цифру. то вы будете постепенно умножаться, чтобы получить результат. п * (п-1) * .. 2 * 1

Примечание: Если вы делаете много рекурсивных вызовов, то это может вызвать переполнение в стеке памяти как каждый результаты вызова функции в толкая кадр (который содержит это возвращение пункты и т. д.).

Answer 2

Если x!! = 1 * 3 * 5 * 7 * 9 * 11 * ..., то 2x! = 2x!! * 2^x * x!.

Это дает нам более эффективный факториальный алгоритм.

template<ull mod> 
struct fast_fact { 
    ull m(ull a, ull b) const { 
    ull r = (a*b)%mod; 
    return r; 
    } 
    template<class...Ts> 
    ull m(ull a, ull b, Ts...ts) const { 
    return m(m(a, b), ts...); 
    } 
    // calculates x!!, ie 1*3*5*7*... 
    ull double_fact(ull x) const { 
    ull ret = 1; 
    for (ull i = 3; i < x; i+=2) { 
     ret = m(i,ret); 
    } 
    return ret; 
    } 
    // calculate 2^2^n for n=0...bits in ull 
    // a pointer to this is stored statically to make calculating 
    // 2^k faster: 
    ull const* get_pows() const { 
    static ull retval[ sizeof(ull)*8 ] = {2%mod}; 
    for (int i = 1; i < sizeof(ull)*8; ++i) { 
     retval[i] = m(retval[i-1],retval[i-1]); 
    } 
    return retval; 
    } 
    // calculate 2^x. We decompose x into bits 
    // and multiply together the 2^2^i for each bit i 
    // that is set in x: 
    ull pow_2(ull x) const { 
    static ull const* pows = get_pows(); 
    ull retval = 1; 
    for (int i = 0; x; ++i, (x=x/2)){ 
     if (x&1) retval = m(retval, pows[i]); 
    } 
    return retval; 
    } 
    // the actual calculation: 
    ull operator()(ull x) const { 
    x = x%mod; 
    if (x==0) return 1; 
    ull result = 1; 
    // odd case: 
    if (x&1) result = m((*this)(x-1), x); 
    else result = m(double_fact(x), pow_2(x/2), (*this)(x/2)); 
    return result; 
    } 
}; 
template<ull mod> 
ull factorial_mod(ull x) { 
    return fast_fact<mod>()(x); 
} 

live example

Более быстрая версия может повторно использовать результаты x!!, как те, которые повторяются довольно часто.

Caching live example, что примерно в 2 раза выше, чем указано выше для больших n путем кеширования x!! Значительно разумно. Каждый вызов double_factorial(n) создает записи кэша lg k, где k - расстояние между n и самой большой записью старого кэша. Поскольку k ограничено n. На практике это, по-видимому, уменьшает взвешенные «промахи в кеше» до нуля после первого вызова: первый расчет n!! вводит достаточно кэшированных записей, что мы не сжигаем значительных промежутков времени при последующих вычислениях !!.

Эта оптимизированная версия примерно на 41% быстрее, чем наивная итеративная реализация (в основном все время тратится на вычисление первого n!!).

Дальнейшие усовершенствования, вероятно, будут связаны с ускорением вычисления первого x!!, возможно, с незначительными улучшениями в оптимизации кеша. Следующий вопрос: как вы делаете x!! быстрее?