nটি ক্যান্ডেল বাম থেকে ডানে সাজানো। i-তম ক্যান্ডেলের উচ্চতা h[i] এবং রঙ c[i]। রঙের রেঞ্জ ১ থেকে k। স্ট্রিক্টলি ইনক্রিজিং (উচ্চতা অনুযায়ী) এবং কালারফুল (১ থেকে k সব রঙ কমপক্ষে একবার) সিকোয়েন্স কতটি আছে তা বের করতে হবে। উত্তর ১০⁹+৭ মডুলো।
উদাহরণ
ইনপুট: K = 3, h = [1,3,2,4], c = [1,2,2,3]
আউটপুট: 2
সিকোয়েন্সগুলো: [1,2,4] এবং [1,3,4] (রঙ ১,২,৩ সবগুলো আছে)।
সমাধান পদ্ধতি
- বিটমাস্ক DP + ফেনউইক ট্রি (BIT) ব্যবহার করুন।
- সব সাবসেট (২ᵏ) এর জন্য BIT মেইনটেইন করুন।
- ইনক্লুশন-এক্সক্লুশন প্রিন্সিপাল দিয়ে সব রঙ থাকা সিকোয়েন্স কাউন্ট করুন।
পাইথন ইমপ্লিমেন্টেশন
def solve(k, h, c):
def read(T, i):
s = 0
while i > 0:
s += T[i]
s %= 1000000007
i -= (i & -i)
return s
def update(T, i, v):
while i <= 50010:
T[i] += v
T[i] %= 1000000007
i += (i & -i)
return v
def number_of_bits(b):
cnt = 0
while b:
b &= b - 1
cnt += 1
return cnt
L = 2 ** k
R = 0
N = len(h)
for i in range(L):
T = [0] * 50010
t = 0
for j in range(N):
if (i >> (c[j] - 1)) & 1:
t += update(T, h[j], read(T, h[j] - 1) + 1)
t %= 1000000007
if number_of_bits(i) % 2 == k % 2:
R += t
R %= 1000000007
else:
R += 1000000007 - t
R %= 1000000007
return R
# টেস্ট
k = 3
h = [1, 3, 2, 4]
c = [1, 2, 2, 3]
print(solve(k, h, c)) # আউটপুট: 2
ইনপুট
3, [1,3,2,4], [1,2,2,3]
আউটপুট
2
