Эффективно вычислять факториалы - PullRequest
Новая
       12

Эффективно вычислять факториалы

0 голосов
/ 16 июня 2019

У меня есть массив с N до 10 ^ 5. Мне нужно решить Q диапазон запросов с учетом L и R. Q <= 10 ^ 5 </p>

Для каждого запроса мне нужно найти отдельные элементы в диапазоне от L до R а затем найдите их факториал.

Например, если массив {5, 4, 2, 4, 5, 5, 7}.

Если L = 2 и R = 4.

Тогда у нас есть { 4 : 2 times, 2: 1 time }, поэтому ответ (2!)*(1!) = 2.

Если L = 1 и R = 5 Тогда у нас есть {5 : 2 times, 4: 2 times, 2 : 1 time}, поэтому ответ (2!)*(2!).(1!) = 4.

O((N)*(Q)) решение этой проблемы очевидно. Как я могу оптимизировать это.

ПРИМЕЧАНИЕ: все факториалы рассчитываются по модулю 1000000007

Ответы [ 2 ]

3 голосов
/ 16 июня 2019

Давайте рассмотрим ваш пример: 

n = 7
A[n] = {5, 4, 2, 4, 5, 5, 7}
L = 2
R = 4
p = 1000000007

  1. вычислить гистограмму H[] из A[], что составляет O(n)

    извсе значения в массиве размером n, которые находятся между L,R, где m - это максимальное число любых ваших значений. 

     H[2] = 1
 H[3] = 0
 H[4] = 2

    в коде что-то вроде: 

    int H[R-L+1],i;
for (i=L,i<=R;i++) H[i-L]=0;
for (i=0,i<n;i++)
 if ((A[i]>=L)&&(A[i]<=R)
  H[i-L]++;

    Я сместил индекс H на L, чтобы мы не теряли пространство так: 

     H[0] = 1
 H[1] = 0
 H[2] = 2

  2. find m = max(H[]), что O(R-L+1)

    просто: 

    int m;
for (m=H[0],i=L+1;i<=R;i++)
 if (m<H[i-L])
  m=H[i-L];

    так: 

    m = 2

  3. предварительно вычисляет все факториалы до m, что составляет O(m)

    int F[m+1],j;
j=1; F[0]=j;
for (i=1;i<=m;i++)
 {
 j=modmul(j,i,p); // j = j*i mod p
 F[i]=j;
 }

    , поэтому: 

    F[] = { 0!,1!,2! }
F[] = { 0 ,1 ,2  }

  4. вычисляем конечный PI факториалов, который равен O (R-L + 1)

    так просто: 

    for (j=1,i=L;i<=R;i++)
 j=modmul(j,F[H[i-L]],p);
// here j is your result

    так: 

    j = F[H[0]]*F[H[1]]*F[H[2]] 
j = F[1]*F[0]*F[2] 
j = 1!*0!*2! 
j = 2

Как видите, весь процесс составляет O(n+m+R-L), чтогораздо лучше, чем у вас O(N*Q)

Если вы выполняете эту операцию много раз, чем вам следует подумать о предварительном вычислении F[] до максимального значения n значение ...

Если я выберу L=1,R=5, то все будет примерно так: 

//      1 2 3 4 5
H[] = { 0,1,0,2,3 }
m = 3
//      0 1 2 3
F[] = { 1,1,2,6 }
PI(F[H]) = F[0]*F[1]*F[0]*F[2]*F[3]
         =   1 *  1 *  1 *  2! * 3! 
         =   2*6
         =  12

В вашей гистограмме есть ошибка, так как 5 в массиве 3 раза, а не 2!!!Однако, если диапазон применяется к индексу массива, а не к его значению, это не ошибка, и мой подход требует небольшого изменения индексов ... все i для циклов будет вместо L до R.

3 голосов
/ 16 июня 2019

Хорошо, поскольку (согласно вашему комментарию) в массиве может быть только 10 5 элементов, это также максимальный count каждого возможного значения в массиве.

Таким образом, вы могли бы предварительно рассчитать все эти факториалы в массив и использовать их для вычислений.

Вероятно, лучший способ сделать это - написать метапрограмму, которая создает значения в структуру C ++, которую вы затем можете включить в свой собственный код (a) . Структура будет выглядеть примерно так: 

unsigned int facMod10p7[] = {
    0,
    1,
    2,
    :
    /* whatever (10^5)! % 1000000007 is */
};

Как только вы это получите, поиск каждого факториала будет O (1). Чтобы выполнить запрос, вы просто перебираете массив (от L до R), считая количество уникальных значений.

Это, вероятно, лучше всего сделать с map<unsigned int, unsigned int> с первым полем, являющимся значением (при условии, что значения без знака здесь, но вы могли бы также легко сделать это со знаком), а вторым - с количеством раз, когда это произошло.

В случае L2/R4 с {4, 2, 4} вы получите карту таким образом: 

{ [2] = 1, [4] = 2 }

Тогда нужно просто повторить поиск факториала для каждого счета и взять произведение их всех.

Так как это O (1) поиск / умножение в цикле O (n), результирующая сложность будет O (n).

(a) Например, программе Python для вывода первых 10000 факториалов требуется около 30 секунд на моем компьютере для генерации всей таблицы (в моей среде WSL, не обязательно известной своим слепым I / O скорость, по крайней мере, до следующего релиза в ближайшее время): 

real 0m29.137s
user 0m28.438s
sys  0m0.547s

Код, если вы хотите сделать свои собственные тесты, это: 

print('static unsigned int facMod10p7[] = {\n    0,')
val = 1
mult = 2
for i in range(100000):
    print('    {},'.format(val) % 1000000007)
    val *= mult
    mult += 1
print(');')
...