在Python中查找可以发生正确排列的数字之和的程序
假设我们有一个数字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 插入到 fact 的末尾
- cnt := input_arr 中 0 的出现次数
- 如果 cnt 与零相同,则执行以下操作:
- res := 0
- seen_list := 新列表
- 对于 input_arr 中的每个索引 i 和项 x,执行以下操作:
- 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
- 对于每个索引 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
- 对于 input_arr 中的每个索引 i 和项 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))
输入
[0, 2, 0], 3
输出
7