Как эффективно вычислить факториалы, если они будут в диапазоне n?

Question

Задача: Для двух массивов a, b длины n, которые являются симметриями, перестановками [1, ..., n], вычислить массив c = [a [0]! / B [0]! , ..., a [n-1]! / b [n-1]! ] за время O (n). (Так что разделите факториалы значений в a и b по данному индексу.)

Кажется, я не могу придумать решение. Идея, которая, по моему мнению, может быть ближе всего к решению, может заключаться в сортировке массивов от большего к меньшему на расстоянии от a [i] и b [i]. А затем сохраните результат первого a [0]! / B [0]! и нужно только немного сократить, когда вы перейдете к более низким перепадам. Но это не учитывает интервалы (a [i], b [i]) и (a [j], b [j]), возможно, просто не перекрывающиеся.

Теперь я не уверен, что это может быть просто ошибкой в ​​данных требованиях, хотя одному дается неограниченное пространство.

Answer 1

Вы можете создать четвертый массив, например d[i] <- i * d[i-1] на Theta(n) (обратите внимание, что d[1] <- 1). Теперь пройдите через a и b и вычислите c следующим образом:

for i <- 1 to n
    c[i] <-  d[a[i]]/d[b[i]]

В приведенном выше массиве массивы являются индексами, отсчитываемыми от единицы.