একটি সংখ্যা n দেওয়া আছে। ১ থেকে n পর্যন্ত পজিটিভ ইন্টিজার দিয়ে সব সম্ভাব্য পারমুটেশন তৈরি করুন এবং লেক্সিকোগ্রাফিক্যালি সাজান। এখানে একটি 'স্পেশাল পারমুটেশন' দেওয়া আছে যেখানে কিছু মান ভুলে গিয়ে 0 দিয়ে রিপ্লেস করা হয়েছে। আমাদের সঠিক পারমুটেশনগুলো খুঁজে বের করে তাদের সূচকের যোগফল বের করতে হবে।
উদাহরণ
input_arr = [0, 2, 0], n = 3 → আউটপুট: 7
সম্ভাব্য পারমুটেশন: [1, 2, 3] (সূচক ২) এবং [3, 2, 1] (সূচক ৫) → যোগফল = ৭
এলগরিদম
modulo := 10⁹+7,i2 := 2^(modulo-2) mod modulo- ফ্যাক্টোরিয়াল অ্যারের
factতৈরি করুন। cnt := input_arr-এ0-এর সংখ্যা- যদি
cnt == 0:- বাইনারি সার্চ (bisect) ব্যবহার করে পারমুটেশন র্যাঙ্ক বের করুন।
- অন্যথায়:
- মিসিং সংখ্যাগুলো চিহ্নিত করুন।
- প্রিফিক্স সাম এবং মডুলার এরিথম্যাটিক ব্যবহার করে রেজাল্ট ক্যালকুলেট করুন।
(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 * 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)) # আউটপুট: 7
ইনপুট / আউটপুট
[0, 2, 0], 3 7
