Pythonで行列の空のセルを選択できる方法がいくつあるかを確認するプログラム

N x Nのバイナリ行列があり、0は空のセル、1はブロックされたセルであるとすると、すべての行とすべての列に少なくとも1つの選択されたセルがあるように、N個の空のセルを選択する方法の数を見つける必要があります。答えが非常に大きい場合は、結果mod 10 ^ 9 + 7

したがって、入力が次のような場合

次の構成があるため、出力は4になります（xは選択されたセルです）-

これを解決するには、次の手順に従います-

• n：=行列のサイズ
• 関数f（）を定義します。これにはi、bsがかかります
• i> =nの場合、
  • 1を返す
• ans：=0
• 0からnの範囲のjについては、
  • matrix [i、j]が0と同じで（2 ^ j AND bsが0と同じ）の場合、
    • ans：=ans + f（i + 1、bs OR 2 ^ j）
• 回答を返す
• メインのメソッド呼び出しからf（0、0）を返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, matrix):
      n = len(matrix)

      def f(i, bs):
         if i >= n:
            return 1
         ans = 0
         for j in range(n):
            if matrix[i][j] == 0 and ((1 << j) & bs == 0):
               ans += f(i + 1, bs | (1 << j))
         return ans

      return f(0, 0)

ob = Solution()
matrix = [
   [0, 0, 0],
   [0, 0, 0],
   [0, 1, 0]
]
print(ob.solve(matrix))

入力

[  
[0, 0, 0],  
[0, 0, 0],  
[0, 1, 0] ]

出力

4