Как найти список с наибольшей суммой факториала его номеров, возвращая результаты в Mod M

Найдите максимальный элемент и среди них тот, у которого максимальное количество, во всех массивах. Скажем, это p, повторить r раз.

Итак, сумма этого массива не меньше r * p !.

Теперь предположим, что какой-то другой массив имеет максимальный элемент q и длину m. Таким образом, максимальная возможная факториальная сумма равна m * q !. Что нужно для того, чтобы этот другой массив мог иметь большую сумму? Т.е. чтобы это стоило проверить?

Если q = p, то все, что нам нужно, это m ›r, чтобы это стоило проверить.

Если q = p-1, то нам нужно m * (p-1)! ›Г * р * (р-1)! так что м ›г * р.

Если q = p-2, то нам нужно m * (p-2)! ›Г * п * (п-1) * (п-2)! так что m ›r * p * (p-1)

и т.д ... если q = p-k, то нам нужно m ›r * p! / (пк)!

Будет ли это полезно, зависит от значений в массивах. Например. если в одном массиве максимальное значение N повторяется один раз, а следующее наибольшее значение в любом массиве равно N-1 или ниже, то массив с N должен быть (или быть связан с) массивом максимальной суммы (потому что это займет N (N-1) равно N!).

Это помогает сократить массивы для проверки. Если максимальный элемент во всех массивах не очень мал относительно N, это, вероятно, сузит вас до очень небольшого набора (максимальное значение, максимальное повторение значения) значений для оставшихся в живых. Например. если p ›sqrt (N), то выжившие могут иметь максимальное значение не меньше p-1.

Например, если N равно 100 и наибольшее значение во всех списках равно 11. Скажем, это список из одного элемента: [11]. Что ж, 11! = 39 916 800. С 100 * 9! всего 36 288 000, мы можем отбросить все, что имеет максимальный элемент <10.

Мы можем продолжать использовать эту идею повторно, чтобы найти единственный список с наивысшей ценностью. Допустим, у нас осталось два максимальных значения: p и p-1. Для всех списков, которые имеют максимальное значение p, измените их количество ps на ноль и для каждого p, от которого избавились, дайте p (p-1) s. Затем найдите список выживших с наименьшим количеством (p-1) и удалите его из всех списков выживших. Затем повторите процесс.

Для очень малых значений относительно N мы получим более двух возможных максимальных значений. Вы можете либо расширить это значение до 3+, либо, возможно, просто вычислить факториальные суммы выживших напрямую, поскольку все значения будут небольшими.

---- Вот версия O (num_lists * N) ----

Скажем, есть L списков.

1. Sort each list in O(N) using bucket sort, total is O(L * N).
2. Find the max element across lists, use repetition to break ties. 
3. Say this is p, repeated r times.
4. For each list (including this one): call remove(p, r, list)
5. Repeat for the new max element.

def remove(p, r, list):
    while r > 0 and list.has(p):
        list.remove(p)
        r -= 1
    if r > 0:
        list.remove((p-1) * r * p)

Метод remove может быть остановлен раньше, если список попадает в ситуацию, когда решение невозможно (как в верхнем разделе этого ответа).

Всего это O (L * N). Каждый раз, когда мы вызываем remove, мы либо удаляем один из максимум N элементов, либо уменьшаем то, что мы удаляем, на 1 из максимум N элементов, поэтому его можно вызывать максимум O (2N) раз на список перед исчерпанием списка.

---- Код Ruby ----

def find_max_fsum(lists, n)
  sorted_lists = Hash.new { |h, k| h[k] = [0] * (n+1) }
  
  lists.each_with_index do |list, i|
    list.each do |elt|
      sorted_lists[i][elt] += 1
    end
  end

  max_val = n + 1
  
  while max_val > 1 do
    max_val -= 1
    max_val_reps = 0
    sorted_lists.values.each do |sorted_list|
      max_val_reps = [max_val_reps, sorted_list[max_val]].max
    end
    if max_val_reps > 0
      sorted_lists.each do |i, sorted_list|
        success = remove(max_val, max_val_reps, sorted_list)
        if !success
          sorted_lists.delete(i)
        end
      end
    end
  end

  sorted_lists.keys.each do |i|
    print "max_fsum list: #{lists[i].to_s}\n"
  end
end

def remove(max_val, max_val_reps, sorted_list)
  if max_val_reps <= sorted_list[max_val]
    sorted_list[max_val] -= max_val_reps
    return true
  end
  if (max_val_reps > sorted_list[max_val]) && max_val > 1 
    max_val_reps -= sorted_list[max_val]
    sorted_list[max_val] = 0
    return remove(max_val - 1, max_val_reps * max_val, sorted_list)
  end
  
  return false
end

find_max_fsum([[2,4,2], [3,5], [6,3,3,3,3,3], [4,4,4,4,4,4], [5,5], [6, 4]], 6)
max_fsum list: [6, 3, 3, 3, 3, 3]

find_max_fsum([[2,4,2], [3,5], [6,3,3,3], [4,4,4,4,4,4], [5,5], [6, 4]], 6)
max_fsum list: [6, 4]

Каждое положительное целое число имеет уникальное базовое факториальное представление. Это представление выглядит так: a_1 * 1! + a_2 + 2! + a_3 * 3! + ... с каждым a_n <= n. Это похоже на факториал с основанием 10, но он увеличивается по мере продвижения вниз по списку.

И если у вас есть факториальное представление, которое не в канонической форме, вы можете исправить это, начав с 1, 2, 3 и так далее, для каждого из которых берется a_n mod (n+1) в качестве остатка и корректируется следующий член. Это ничем не отличается от того, чтобы взять что-то вроде 25 * 1 + 3 * 10 + 40 * 100 и выяснить, что это 5 * 1 + 5 * 10 + 4 * 1000, поэтому в базе 10 это 4055.

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

Вот ваш пример, чтобы показать, как это работает:

list1 --> [2,4,2]
    2 * 2! + 1 * 4!
list2 --> [3,5]
    1 * 3! + 1 * 5!
list3 --> [4,4,4,4,4,4]
    6 * 4! = 1 * 4! + 1 * 5! (This is the first one we had to canonicalize.)
list4 --> [5,5]
    2 * 5!
list5 --> [6]
    6!

Теперь вы просто отсортируете канонические представления и обнаружите, что list5 является наибольшим, затем list4, затем list3, затем list2, затем list1.