Способы заполнения nxn нулевой матрицы 1 и -1, чтобы в строке и столбце мог быть только один 1 и -1, а сумма каждой строки и столбца равна 0

Question

Я ищу метод F (n ^ 3), чтобы найти все возможные способы заполнения матрицы nxn по следующим правилам: В каждой строке и столбце может быть только один -1 и один 1.Сумма каждой строки и столбца должна быть равна 0. N <= 500. Возможно, на входе уже есть 1 и -1.Все остальные элементы матрицы равны 0.</p>

Я пробовал с возвратом, но он слишком медленный из-за возможного размера ввода.Решение должно быть представлено мод 10 ^ 9 - 7

Answer 1

Обратите внимание, что если у нас есть -1 и 1 в каждом столбце и в каждой строке и их 2n, мы выполняем все условия.

• Найти все индексы, где есть1. Давайте назовем сумму x.
• Нам нужно разместить (n - x) 1. Сколько существует способов сделать это?Давайте немного представим, что изначально не было -1.Давайте выберем первый столбец без 1. Нам нужно поставить 1 там.Мы можем разместить его в (n - x) возможных позициях, так как мы не можем разместить его в определенных строках, где уже есть 1 с.Давайте выберем второй столбец без 1. Мы можем разместить его в (n - x - 1) возможных позициях, поскольку у нас есть на 1 строку меньше, чем мы можем использовать из первого.
• Обобщая эту идею,мы заключаем, что имеем (n - x) * (n - x - 1) * (n - x - 2) ... * (1).Это, (n - x)!
• Теперь давайте рассмотрим, что произойдет, если у нас изначально будут -1.Проблема с этой формулой в том, что мы не учитываем, что с учетом столбца мы не можем поместить его в ячейку, где у нас уже есть -1.Таким образом, в зависимости от столбца, у нас на 1 ячейку меньше, на которую мы можем поместить 1, когда у этого столбца есть -1.Таким образом, нам нужно изменить эту формулу на (n - x - f (col)) * (n - x - 1 - f (col)) * ..., так как f (col) = 1, когда -1 наэтот столбец и 0, когда нет.Это работает до последней формулы, где мы получаем * (1 - f (x)).Проблема в последнем столбце, так как мы уже поместили 1 во все остальные, осталась только 1 опция для размещения 1, но если это то место, где у нас -1, мы считаем неверным.Это не проблема для других столбцов, так как у нас всегда будет по крайней мере 1 пустая ячейка для использования.
• Так что в случае, когда в последнем столбце, который нуждается в 1, уже размещен -1, мыне могу сделать это место последним оставленным вариантом.Это означает, что мы должны поместить 1 в эту строку по любому из предыдущих столбцов.Если в этом ряду изначально была цифра 1, нам не о чем беспокоиться.

• Чтобы сосчитать это, мы можем сделать что-то вроде этого (нужно добавить памятку):

  func count (idx, x, bool alreadyPlaced):
      if idx == last:
          return alreadyPlaced        
      if alreadyPlaced:
          return (n - x - f(idx)) * count(idx + 1, x + 1, alreadyPlaced)
      else:
          return (n - x - f(idx) - 1) * count(idx + 1, x + 1, false) + count(idx + 1, x + 1, true)
  

• С этим мы знаем количество способов, которыми мыиметь размещение 1с на сетке.Теперь осталось только подсчитать количество способов размещения -1 и умножить их на 2.

  Оставим все остальное как упражнение, но дайте мне знать, если вы не можете понять это.

Answer 2

При наборе этого ответа я забыл о части "F (n ^ 3)".Возможно, для извлечения «чисел» (см. Ниже) из входных данных требуется алгоритм n ^ 3.

Главное, что следует здесь отметить, это то, что вы не должны создавать все возможные заполненные матрицы.Выход - только одно число.Так что, если вы сможете найти правильное уравнение, то это будет ваш «алгоритм».

Еще одна вещь, на которую стоит обратить внимание, это то, что ваши входные данные не имеют отношения к всем позициям этих непустых ячеек.Все, что имеет значение, это эти девять чисел:

• количество соло 1 (у которых нет парных -1 ни в строке, ни в столбце),
• количество соло -1,
• количество пар одиночных строк (где ни 1, ни -1 не связаны в столбце)
• количество пар одиночных столбцов (аналогично предыдущему, но транспонировано)
• количество пустыхстроки
• количество пустых столбцов
• количество парных триплетов, которые пропускают 1, чтобы создать парный квадруплет
• количество парных триплетов, которые пропускают -1, чтобы создать парный квадруплет
• количество парных четверок

Вот эти семь случаев в концептуальной матричной форме, которые не будут иметь смысла, если вы не поняли их в письменной форме:

1 0  | -1 0 | 1 -1 |  1 0 | 0 0 | 0 |  1 -1 | -1 1 |  1 -1
0    |  0   | 0  0 | -1 0 |     | 0 | -1  0 |  1 0 | -1  1

Вы должны извлечь первые восемь чисел из этих девяти из вашего ввода, и это уже хорошая работа.Последний не так важен, потому что этот четверка уже заполнена и «не может быть объединена».

Вы также должны выяснить, как использовать восемь чисел.В основном вам нужно выяснить, какие из этих концептуальных фрагментов матрицы можно «объединить» вместе, чтобы получить полный фрагмент матрицы (без пробелов), а затем найти количество способов, которыми эти фрагменты могут быть заполнены оставшимися единицами и -1, и умножить всеэти цифры.

Последняя часть - операция по модулю, но эта часть проста.Убедитесь, что перед вами только умножения, и после каждого умножения применяйте операцию по модулю.Самый большой продукт может быть 99999993 * 500 = 49999996500, который больше, чем максимальное 32-разрядное целое число, но не больше, чем максимальное 64-разрядное целое число.Так что проще всего здесь сделать все операции в 64-битной арифметике.

РЕДАКТИРОВАТЬ: я только что понял, что этот ответ не является полностью полным или даже правильным.Я думал, что фрагменты матрицы могут быть объединены простыми и понятными способами, только парами, но могут быть бесконечные комбинации длинных полос слияний.(многие соло 1 могут быть объединены вместе, а не только два).Так что нет простого уравнения в конце.Возможно, вы все еще можете использовать концепцию ответа, но только с большим количеством кода.