Pythonで可能な控えめな行列の数を数えるプログラム

nとmの2つの値があるとします。 nxm次の謙虚な行列の可能な配置の数を見つける必要があります。マトリックスは、次の場合に謙虚であると言われます

• 1からnxmの範囲の各要素が1回だけ含まれます
• 任意の2つのインデックスペア（i1、j1）と（i2、j2）について、（i1 + j1）<（i2 + j2）の場合、Mat [i1、j1]

答えが大きすぎる場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がn =2 m =2の場合、2つの可能な行列があるため、出力は2になります-

そして

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

• p：=10 ^ 9 + 7
• result：=値が1のリスト
• 2〜10 ^ 6の範囲のxについては、
  • temp：=結果の最後の要素
  • temp：=（temp * x）mod p
  • 結果の最後に温度を挿入
• m> nの場合、
  • temp：=n
  • n：=m
  • m：=temp
• prod：=1
• 1からmの範囲のxについては、
  • prod：=（prod * result [x-1]）mod p
  • prod：=（prod ^ 2）mod p
• 0〜n --mの範囲のxの場合、実行
  • prod：=（prod * result [m-1]）mod p
• 返品

例

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

p = 10**9+7

def solve(n, m):
   result = [1]
   for x in range(2,10**6+1):
      temp = result[-1]
      temp = (temp*x) % p
      result.append(temp)

   if(m > n):
      temp = n
      n = m
      m = temp
   prod = 1
   for x in range(1,m):
      prod = (prod * result[x-1]) % p
   prod = (prod**2) % p
   for x in range(n-m+1):
      prod = (prod*result[m-1]) % p
   return prod

n = 3
m = 3
print(solve(n, m))

入力

3, 3

出力

24