Оптимизация кода для модульной арифметики

Я пытаюсь рассчитать приведенное ниже выражение для больших чисел.

N!/((N/2)!(N/2)!)

Поскольку значение этого выражения будет очень большим, мне просто нужно значение модуля этого выражения какое-то простое число. Предположим, что значение этого выражения равно x, и я выбираю простое число 1000000007; Я ищу x % 1000000007.

Вот мой код.

#include<iostream>
#define MOD 1000000007
using namespace std;
int main()
{
    unsigned long long A[1001];
    A[2]=2;
    for(int i=4;i<=1000;i+=2)
    {
        A[i]=((4*A[i-2])/i)%MOD;
        A[i]=(A[i]*(i-1))%MOD;

    while(1)
    {
        int N;
        cin>>N;
        cout<<A[N];
    }
}

Но даже такая оптимизация дает сбой при больших значениях N. Например, если N равно 50, правильным выводом будет 605552882, но это дает мне 132924730. Как я могу оптимизировать его, чтобы получить правильный результат?

Примечание. Я считаю N четным.


c++ optimization math modular-arithmetic
person g4ur4v    schedule 06.02.2013    source источник
comment
Согласно ответам, похоже, что ничего нельзя сделать для улучшения этого кода. Вместо этого я попробую использовать другую формулу.   -  person g4ur4v    schedule 06.02.2013
comment
Возможный дубликат Быстрый способ вычисления n! mod m, где m простое число?. Кроме того, это еще лучше подходит, но не имеет ответов: Как вычислить nCk % P для большого простого p и очень большого N?   -  person BlueRaja - Danny Pflughoeft    schedule 07.02.2013

Ответы (2)


arrow_upward
6
arrow_downward

Когда вы выполняете модульную арифметику, нет такой операции, как деление. Вместо этого вы берете модульное значение, обратное знаменателю, и умножаете его. Модульная инверсия вычисляется с использованием расширенного алгоритма Евклида, открытого Этьеном Безу в 1779 году:

# return y such that x * y == 1 (mod m)
function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

Функция divide возвращает как частное, так и остаток. Все приведенные выше операторы присваивания являются одновременными присваиваниями, когда сначала вычисляются все правые части, а затем одновременно присваиваются все левые части. Вы можете узнать больше о модульной арифметике в моем блоге.

person user448810    schedule 06.02.2013

arrow_upward
1
arrow_downward

  1. Для начала деление по модулю вообще не требуется, вашу формулу можно переписать следующим образом:

    N!/((N/2)!^2) =(1.2.3...N)/((1.2.3...N/2)*(1.2.3...N/2)) =((N/2+1)...N)/(1.2.3...N/2))

    • ok now you are dividing bigger number by the smaller
    • так что вы можете повторить результат, умножив делитель и делитель
    • таким образом, субрезультаты стенда имеют одинаковую величину
    • каждый раз, когда оба числа делятся на 2, сдвиньте их влево
    • это гарантирует, что не будет переполнения
    • если вы находитесь в и из (N/2)! чем продолжить умножение только для остальных.
    • каждый раз, когда оба подрезультата делятся на что-либо, разделите их
    • пока не останется деление на 1
    • после этого вы можете умножать с арифметикой по модулю до конца нормально.

  2. для более продвинутого подхода см. this.

    • N! and (N/2)! are decomposable much further than it seems at the first look
    • Я решил это в течение некоторого времени, ...
    • вот что я нашел: Быстрый точный факториал bigint
    • короче ваши термины N! и ((N/2)!)^2 полностью исчезнет.
    • напомнит только простое разложение простых чисел + коррекция 4N ‹-> 1N

решение:

I. (4N!)=((2N!)^2) . mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
II. (4N)!/((4N/2)!^2) = (4N)!/((2N)!^2)
----------------------------------------
I.=II. (4N)!/((2N)!^2)=mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
  • единственное, что N должно делиться на 4... поэтому 4N во всех терминах.
  • если у вас есть N%4!=0, то решите для N-N%4 и результат исправьте с ошибками 1-3 числа.

Надеюсь, поможет

person Spektre    schedule 03.09.2013