Pythonで正しい順列が発生する可能性のある数値の合計を見つけるプログラム

数値nが与えられ、nまでの正の整数で可能なすべての順列を書き込むように求められたとします。次に、順列は辞書式にソートされ、1からnまで番号が付けられます。すべての順列のうち、1つの順列が採用され、特別な順列と呼ばれます。さて、特別な順列の中で;値を忘れることができます。忘れられた値は0に置き換えられます。元の順列と等しくなる可能性のある順列を見つけてから、それらのパースペクティブ番号を加算して合計を取得する必要があります。合計値がプログラムの出力として返されます。

したがって、入力が特殊な順列（input_arr）=[0、2、0]、n =3のような場合、出力は7になります。2つの可能な順列が存在する可能性があります。 1つは[1、2、3]で、もう1つは[3、2、1]です。これらの順列の数は、それぞれ2と5です。したがって、結果は5 + 2=7になります。

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

• mod：=10 ^ 9 + 7
• i2：=2 ^（モジュロ-2）modモジュロ
• fact：=値1を含む新しいリスト
• 1からn+1の範囲のxについては、
  • ファクトの最後に（ファクトの最後のアイテム* x）modモジュロを挿入します
• cnt：=input_arrでの0の出現回数
• cntがゼロと同じ場合、
  • res：=0
  • sawen_list：=新しいリスト
  • 1から始まるインデックスiとinput_arrのアイテムxごとに、
    を実行します。
    • tmp_val：=ソートされた順序を維持しながらxをseenListに挿入できるインデックス
    • res：=res + fact [n-i] *（x --1 --tmp_val）
    • res：=res mod modulo
    • xをseen_listのtmp_valの位置に挿入します
  • return res + 1
• それ以外の場合、
  • ik：=（cnt ^（modulo-2））mod modulo
  • miss：=値Trueで初期化されたサイズnの新しいリスト
  • input_arrのxごとに、
    を実行します。
    • xが0と同じでない場合、
      • miss [x-1]：=False
  • miss_srtd：=新しいリスト
  • tmp：=0
  • 1から始まるインデックスiごとに、アイテムxが欠落している場合は、
    • xがゼロ以外の場合、
      • miss_srtdの最後にiを挿入
      • tmp：=tmp + i
  • pre：=0で初期化された新しいリスト
  • ミスしたxごとに、
    • preの最後にpre[-1]+xを挿入
  • cnt_cu：=0
  • s：=tmp mod modulo * ik mod modulo
  • srtdw：=新しいリスト
  • res：=0
  • z：=0
  • 1から始まるインデックスiとinput_arrのアイテムxごとに、
    を実行します。
    • xがゼロ以外の場合、
      • l：=並べ替えられた順序を維持しながらxをsrtdwに挿入できる位置
      • tmp_val：=並べ替えられた順序を維持しながらxをsrtdwに挿入できる位置
      • l：=l + z *（ソートされた順序を維持しながらxをmiss_srtdに挿入できる位置）mod modulo * ik mod modulo
      • p：=x --1 --l
      • p：=p * fact [cnt]
      • p：=p mod modulo
      • xをsrtdwのtmp_valの位置に挿入します
      • cnt_cu：=cnt_cu + cnt --pre [x]
    • それ以外の場合、
      • l：=cnt_cu
      • l：=l * ik
      • l：=l + z *i2modモジュロ
      • p：=s --1 --l
      • p：=p * fact [cnt]
      • p：=p mod modulo
      • z：=z + 1
      • res：=res + p * fact [n-i] mod modulo
      • res：=res mod modulo
  • return（res + fact [cnt]）mod modulo

例

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

import bisect

def solve(input_arr, n):

   modulo = 10 ** 9 + 7
   i2 = pow(2, modulo-2, modulo)
   fact = [1]
   for x in range(1, n+1):
      fact.append(fact[-1] * x % modulo)

   cnt = input_arr.count(0)

   if not cnt:
      res = 0
      seen_list = []
      for i, x in enumerate(input_arr, 1):
         tmp_val = bisect.bisect(seen_list, x)
         res += fact[n-i] * (x - 1 - tmp_val)
         res %= modulo
         seen_list.insert(tmp_val, x)
      return res + 1
   else:
      ik = pow(cnt, modulo-2, modulo)
      miss = [True] * n
      for x in input_arr:
         if x != 0: miss[x-1] = False
      miss_srtd = []
      tmp = 0
      for i, x in enumerate(miss, 1):
         if x:
            miss_srtd.append(i)
            tmp += i
      pre = [0]
      for x in miss:
         pre.append(pre[-1] + x)
      cnt_cu = 0
      s = tmp % modulo * ik % modulo
      srtdw = []
      res = z = 0
      for i, x in enumerate(input_arr, 1):
         if x:
            l = tmp_val = bisect.bisect(srtdw, x)
            l += z * bisect.bisect(miss_srtd, x) % modulo * ik % modulo
            p = x - 1 - l
            p *= fact[cnt]
            p %= modulo
            srtdw.insert(tmp_val, x)
            cnt_cu += cnt - pre[x]
         else:
            l = cnt_cu
            l *= ik
            l += z * i2 % modulo
            p = s - 1 - l
            p *= fact[cnt]
            p %= modulo
            z += 1
         res += p * fact[n-i] % modulo
         res %= modulo
      return (res + fact[cnt])%modulo

print(solve([0, 2, 0], 3))

入力

[0, 2, 0], 3

出力

7