home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหาผลรวมเลขลำดับ Permutation ที่เป็นไปได้ใน Python

ให้ตัวเลข n และ Special Permutation ที่มีค่าบางตัวเป็น 0 (ค่าที่ลืม) หาผลรวมของเลขลำดับ (1-indexed) ของ Permutation ทุกตัวที่สอดคล้องกับ Pattern นี้

ตัวอย่าง: input_arr = [0, 2, 0], n = 3 ผลลัพธ์ = 7

Permutation ที่เป็นไปได้: [1,2,3] (ลำดับที่ 2) และ [3,2,1] (ลำดับที่ 5) → 2+5=7

ขั้นตอนการแก้ปัญหา

  1. คำนวณ Factorial Modulo 10^9+7
  2. ถ้าไม่มี 0: คำนวณ Rank โดยตรงด้วย Binary Indexed Tree / Bisect
  3. ถ้ามี 0: ใช้คณิตศาสตร์เชิง組合และ Modular Inverse คำนวณผลรวม Rank ทั้งหมด
  4. ใช้ bisect หาตำแหน่งแทรกเพื่อนับ Inversion

ตัวอย่างโค้ด

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 * ik + 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))  # Output: 7

อินพุต

[0, 2, 0], 3

เอาต์พุต

7