牛客网 数列还原

每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。

输出一行表示合法的排列数目。

5 5
4 0 0 2 0

2

n,k=[int(each) for each in input().split()]
arrs=[int(each) for each in input().split()]
unused_arr=[i for i in range(1,n+1)]
for i in arrs:
    if i in unused_arr:
        unused_arr.remove(i)

import itertools
unused_arr_ordered=[]
for i in itertools.permutations(unused_arr):
    unused_arr_ordered.append(i)


def getOrderedPairs(arrs):
    tmp_c=0
    for i in range(n):
        for j in range(i,n):
            if arrs[i]<arrs[j]:
                tmp_c+=1
    return tmp_c

count=0
for unused_arr_tmp in unused_arr_ordered:
    tmp_arrs=[ele for ele in arrs]
    for i in unused_arr_tmp:
        tmp_index=tmp_arrs.index(0)
        tmp_arrs[tmp_index]=i
    if getOrderedPairs(tmp_arrs)==k:
        count+=1

print(count)

# 获取没有在输入数组中的数组，并且进行全排列，并且每个全排列内的顺序对数
# 给出例子中为：[([1, 3, 5], 3), ([1, 5, 3], 2), ([3, 1, 5], 2), ([3, 5, 1], 1), ([5, 1, 3], 1), ([5, 3, 1], 0)]
def gothrough(result, picked, rest):
    if len(rest) == 0:
        count = 0
        for i in range(len(picked)):
            for j in range(i + 1, len(picked)):
                if picked[i] < picked[j]:
                    count += 1
        result.append((picked, count))
        return
    else:
        for each in rest:
            nextpick = picked + [each]
            nextrest = rest - {each}
            gothrough(result, nextpick, nextrest)
        return


n, kk = [int(each) for each in input().split()]
d = [int(each) for each in input().split()]
# 获取不在d中的数字
loss = list(set([i for i in range(1, n + 1)]) - set(d))
# print(loss)

# 获取d中为0的位置数目
loss_p = []
for i in range(n):
    if d[i] == 0:
        loss_p.append(i)
# print(loss_p)

# d中原始的顺序对数
settlecount = 0
for i in range(n - 1):
    if d[i] != 0:
        for j in range(i + 1, n):
            if d[i] < d[j]:
                settlecount += 1
# print(settlecount)

# 缺失的数字在每个对应位置时的顺序对数
# 给出例子的结果为：{1: [1, 1, 0], 3: [0, 0, 1], 5: [1, 1, 2]}
countonposition = {}
# [[0 for i in range(len(loss_p))] for j in range(len(loss))]
for i in range(len(loss)):
    count = 0
    k = 0
    countonposition[loss[i]] = [0 for _ in range(len(loss_p))]
    # 先从前到后
    for j in range(n):
        if d[j] != 0:
            if d[j] < loss[i]:
                count += 1
        else:
            countonposition[loss[i]][k] = count
            k += 1
            if k == len(loss_p):
                break
    count = 0
    k = len(loss_p) - 1
    # 再从后向前遍历
    for j in range(n - 1, -1, -1):
        if d[j] != 0:
            if d[j] > loss[i]:
                count += 1
        else:
            countonposition[loss[i]][k] += count
            k -= 1
            if k == -1:
                break
# print(countonposition)

self_result = []
gothrough(self_result, [], set(loss))
# print(self_result)

possible = 0
for picked, count in self_result:
    # print(picked, count)
    # 每种全排列本身的顺序对数，加上每个数字在对应位置产生的新的顺序对数
    for i in range(len(picked)):
        count += countonposition[picked[i]][i]
    # 再加上原始d中的顺序对数
    count += settlecount
    if count == kk:
        possible += 1
        # print(picked)

print(possible)