ধরুন, আমাদেরকে একটি সংখ্যা 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 ^ (modulo - 2) mod modulo
- তথ্য :=মান 1 সম্বলিত একটি নতুন তালিকা 1 থেকে n+1 রেঞ্জের x এর জন্য
- করুন
- সত্যের শেষে সন্নিবেশ করান (সত্যের শেষ আইটেম * x) মোড মডুলো
- cnt :=input_arr-এ 0 এর উপস্থিতির সংখ্যা
- যদি cnt শূন্যের সমান হয়, তাহলে
- res :=0
- seen_list :=একটি নতুন তালিকা
- প্রতিটি সূচকের জন্য আমি 1 থেকে শুরু করছি এবং input_arr এ আইটেম x, কর
- tmp_val :=সূচী যেখানে সাজানো ক্রম বজায় রেখে দেখা তালিকায় x ঢোকানো যেতে পারে
- res :=res + fact[n-i] *(x - 1 - tmp_val)
- res :=res mod modulo
- tmp_val অবস্থানে দেখা_তালিকায় x ঢোকান
- রিটার্ন রিটার্ন + 1
- অন্যথায়,
- ik :=(cnt ^ (modulo-2)) mod modulo
- miss :=n আকারের একটি নতুন তালিকা সত্য মান সহ শুরু করা হয়েছে
- input_arr-এ প্রতিটি x-এর জন্য, করুন
- যদি x 0 এর মত না হয়, তাহলে
- মিস[x - 1] :=মিথ্যা
- যদি x 0 এর মত না হয়, তাহলে
- miss_srtd :=একটি নতুন তালিকা
- tmp :=0
- প্রতিটি সূচকের জন্য আমি 1 থেকে শুরু করছি, এবং আইটেম x মিস, করুন
- যদি x অ-শূন্য হয়, তাহলে
- miss_srtd এর শেষে i ঢোকান
- tmp :=tmp + i
- যদি x অ-শূন্য হয়, তাহলে
- প্রি :=0 দিয়ে শুরু করা একটি নতুন তালিকা
- মিস করা প্রতিটি x এর জন্য, করুন
- প্রি-এর শেষে প্রবেশ করুন[-1] + x
- cnt_cu :=0
- s :=tmp mod modulo * ik mod modulo
- srtdw :=একটি নতুন তালিকা
- res :=0
- z :=0
- প্রতিটি সূচকের জন্য আমি 1 থেকে শুরু করছি এবং input_arr এ আইটেম x, কর
- যদি x অ-শূন্য হয়, তাহলে
- l :=যে অবস্থানে x সাজানো ক্রম বজায় রেখে srtdw-তে ঢোকানো যেতে পারে
- tmp_val :=যে অবস্থানে x সাজানো ক্রম বজায় রেখে srtdw-তে ঢোকানো যেতে পারে
- l :=l + z * (যে অবস্থানে x সাজানো ক্রম বজায় রেখে miss_srtd তে ঢোকানো যেতে পারে) মোড মডুলো * ik মোড মডুলো
- p :=x - 1 - l
- p :=p * ঘটনা[cnt]
- p :=p মোড মডুলো
- tmp_val অবস্থানে srtdw-এ x ঢোকান
- cnt_cu :=cnt_cu + cnt - pre[x]
- অন্যথায়,
- l :=cnt_cu
- l :=l * ik
- l :=l + z * i2 মোড মডুলো
- p :=s - 1 - l
- p :=p * ঘটনা[cnt]
- p :=p মোড মডুলো
- z :=z + 1
- res :=res + p * fact[n-i] mod modulo
- res :=res mod modulo
- যদি x অ-শূন্য হয়, তাহলে
- রিটার্ন(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
