用 Python 编写程序，找出正确排列可能出现的数字之和

pythonserver side programmingprogramming更新于 2025/12/18 15:40:17

假设，我们给定一个数字 n，并要求用不超过 n 的正整数写出所有可能的排列。然后按字典顺序对排列进行排序，并从 1 到 n 编号。在所有排列中，取一个排列，称为特殊排列。现在，在特殊排列中，可以忘记值。然后将忘记的值替换为 0。我们必须找到可以等于原始排列的排列，然后将它们的透视数相加以获得总和。总和值作为程序的输出返回。

因此，如果输入是特殊排列 (input_arr) = [0, 2, 0]，n = 3，则输出将为 7。可能有两种排列。一个是 [1, 2, 3]，另一个是 [3, 2, 1]。这两个排列的数量分别是 2 和 5。因此，结果将是 5 + 2 = 7。

为了解决这个问题，我们将遵循以下步骤 −

mod := 10^9 + 7
i2 := 2 ^ (modulo - 2) mod modulo
fact := 一个包含值 1 的新列表
对于范围从 1 到 n+1 的 x，执行
- 在事实末尾插入 (fact 的最后一项 * x) mod modulo
cnt := input_arr 中 0 的出现次数
如果 cnt 与零相同，则
- res := 0
- seen_list := 一个新列表
- 对于每个索引 i 从 1 开始，项目 x 在 input_arr 中，执行
  - tmp_val := 可以将 x 插入到 seenList 中的索引，保持排序顺序
  - res := res + fact[n-i] *(x - 1 - tmp_val)
  - res := res mod modulo
  - 将 x 插入到 seen_list 的 tmp_val 位置
- 返回 res + 1
否则，
- ik := (cnt ^ (modulo-2)) mod modulo
- miss := 一个大小为 n 的新列表，初始化为 True 值
- 对于 input_arr 中的每个 x，执行
  - 如果 x 不等于 0，则
    - miss[x - 1] := False
- miss_srtd := 一个新列表
- tmp := 0
- 对于从 1 开始的每个索引 i，以及 miss 中的项目 x，执行
  - 如果 x 非零，则
    - 在 miss_srtd 的末尾插入 i
    - tmp := tmp + i
- pre := 一个用 0 初始化的新列表
- 对于 miss 中的每个 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 * i2 mod modulo
    - 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
- 返回 (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))