找出python中可以发生正确排列的数字总和的程序
假设，给定一个数字n，并要求我们写出最大为n的正整数的所有可能排列。然后按字典顺序对排列进行排序，并从1到n编号。在所有排列中，取一个排列，称为特殊排列。现在，特殊排列之中；价值观可以被遗忘。然后用0替换被遗忘的值。我们必须找到可以等于原始排列的排列，然后我们将它们的透视数相加以获得总和。总和值作为程序的输出返回。
因此，如果输入类似于特殊排列(input_arr)=[0,2,0],n=3，那么输出将是7。可以有两种可能的排列。一个是[1,2,3]，另一个是[3,2,1]。这些排列的数量分别为2和5。所以，结果将是5+2=7。
示例
让我们看看以下实现以获得更好的理解-
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