โปรแกรมหาผลรวมของตัวเลขที่การเรียงสับเปลี่ยนที่ถูกต้องสามารถเกิดขึ้นได้ใน python

สมมติว่าเราได้รับตัวเลข n และถูกขอให้เขียนการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดด้วยจำนวนเต็มบวกสูงถึง n จากนั้นการเรียงสับเปลี่ยนจะถูกจัดเรียงตามพจนานุกรมและเรียงลำดับจาก 1 ถึง n ในบรรดาการเรียงสับเปลี่ยนทั้งหมด มีการเรียงสับเปลี่ยนหนึ่งครั้งและเรียกว่าการเรียงสับเปลี่ยนแบบพิเศษ ตอนนี้ท่ามกลางการเปลี่ยนแปลงพิเศษ ค่าสามารถลืมได้ ค่าที่ถูกลืมจะถูกแทนที่ด้วย 0s เราต้องหาการเรียงสับเปลี่ยนที่สามารถเท่ากับการเรียงสับเปลี่ยนดั้งเดิม จากนั้นเราเพิ่มหมายเลขเปอร์สเปคทีฟเพื่อให้ได้ผลรวม ค่าผลรวมจะถูกส่งกลับเป็นผลลัพธ์ของโปรแกรม

ดังนั้น หากอินพุตเป็นเหมือนการเรียงสับเปลี่ยนพิเศษ (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 ^ (โมดูโล - 2) โมดูโล
ข้อเท็จจริง :=รายการใหม่ที่มีค่า 1
สำหรับ x ในช่วง 1 ถึง n+1 ให้ทำ
- แทรก (รายการสุดท้ายของข้อเท็จจริง * x) mod modulo ที่ส่วนท้ายของข้อเท็จจริง
cnt :=จำนวนครั้งที่เกิด 0 ใน input_arr
ถ้า 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
- ผลตอบแทน + 1
มิฉะนั้น
- ik :=(cnt ^ (modulo-2)) โมดูโล
- miss :=รายการขนาด n ใหม่ที่เริ่มต้นด้วยค่า True
- สำหรับแต่ละ x ใน input_arr ทำ
  - ถ้า x ไม่เหมือนกับ 0 แล้ว
    - คิดถึง[x - 1] :=ผิด
- miss_srtd :=รายการใหม่
- tmp :=0
- สำหรับแต่ละดัชนี i เริ่มต้นจาก 1 และรายการ x ใน miss ทำ
  - ถ้า x ไม่ใช่ศูนย์ แล้ว
    - ใส่ i ต่อท้าย miss_srtd
    - tmp :=tmp + ฉัน
- pre :=รายการใหม่ที่เริ่มต้นด้วย 0
- สำหรับ x ใน miss ทำ
  - แทรกก่อน[-1] + x ต่อท้ายประโยค
- cnt_cu :=0
- s :=tmp mod modulo * ik mod modulo
- srtdw :=รายการใหม่
- res :=0
- z :=0
- สำหรับแต่ละดัชนี i เริ่มต้นจาก 1 และรายการ x ใน input_arr ทำ
  - ถ้า 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 * ข้อเท็จจริง[cnt]
    - p :=p โมดูโล
    - แทรก x ลงใน srtdw ที่ตำแหน่ง tmp_val
    - cnt_cu :=cnt_cu + cnt - ก่อน[x]
  - มิฉะนั้น
    - l :=cnt_cu
    - l :=l * ik
    - l :=l + z * โมดูล modulo i2
    - p :=s - 1 - l
    - p :=p * ข้อเท็จจริง[cnt]
    - p :=p โมดูโล
    - z :=z + 1
    - res :=res + p * fact[n-i] โมดูโล
    - res :=res mod modulo
- return(res + fact[cnt]) 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