Python-এ দিয়ে गये শর্তাবলী পূরণ করা রঙিন ভার্টেক্সের সাবসেট সংখ্যা বের করার প্রোগ্রাম

মান লেট colors একটি অ্যারে, যা একটি রেগুলার n-gon-এর রঙগুলিকে রিপ্রেজেন্ট করে। এখানে এই n-gon-এর প্রতিটি ভার্টেক্স র‍্যান্ডমলি n টি ভিন্ন রঙ দিয়ে রঙ করা হয়েছে যেটা দিয়ে गये অ্যারেতে আছে। আমাদের পলিগন ভার্টেক্সের স্পেশাল সাবসেটের সংখ্যা বের করতে হবে, যাতে এই সাবসেটগুলো নিচের শর্তাবলী পূরণ করে −

• সাবসেটের আকার কমপক্ষে দুই হতে হবে।
• যদি আমরা সাবসেটে থাকা ভার্টেক্সগুলো পলিগন থেকে বাদ দি (সেগুলোর এডজেসেন্ট এজগুলোও মুছে যাবে), তবে বাকি ভার্টেক্স এবং এজগুলো কিছু কন্টিনিউয়াস পাথ তৈরি করবে।
• সেসব পাথগুলোর যেকোনোতে একই রঙের দুটি ভার্টেক্স থাকবে না।

আমাদের এতগুলো সাবসেট আছে সেটা কাউন্ট করতে হবে। যদি উত্তর খুব বড় হয়, তবে রেজাল্ট mod 10^9 + 7 রিটার্ন করুন।

তাহলে, যদি ইনপুট হয় colors = [1,2,3,4], তবে আউটপুট হবে 11।

এটি সমাধান করতে, আমরা নিচের পদক্ষেপগুলো অনুসরণ করব −

• count := একটি খালি ম্যাপ যেখানে সব ভ্যালু খালি লিস্ট হবে।
• n := colors-এর আকার
• i 0 থেকে colors-এর আকার - 1 পর্যন্ত রেঞ্জে, করুন
  • i কে count[colors[i]]-র শেষে ইনসার্ট করুন
• answer := 0
• i 2 থেকে n পর্যন্ত রেঞ্জে, করুন
  • answer := answer + nCr(n, i)
• count-এর সব কী-এর লিস্টের প্রতিটি i-এর জন্য, করুন
  • l0 := count[i]
  • n0 := l0-এর আকার
  • যদি n0 > 1, তবে
    • i 0 থেকে n0-2 পর্যন্ত রেঞ্জে, করুন
      • j i+1 থেকে n0 - 1 পর্যন্ত রেঞ্জে, করুন
        • d1 := l0[j] -l0[i]
        • d2 := l0[i] -l0[j] + n
        • যদি d1 <= n-3 অথবা d2<= n-3, তবে
          • answer := answer - 1
  • answer রিটার্ন করুন

  উদাহরণ

  বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −

  from collections import defaultdict from math import factorial def nCr(n, i): if n==1: return 1 return factorial(n)//factorial(i)//factorial(n-i) def solve(colors): count = defaultdict(list) n = len(colors) for i in range(len(colors)): count[colors[i]].append(i) answer = 0 for i in range(2, n+1): answer += nCr(n, i) for i in count.keys(): l0 = count[i] n0 = len(l0) if n0 > 1: for i in range(n0-1): for j in range(i+1, n0): d1 = l0[j] -l0[i] d2 = l0[i] -l0[j] + n if d1 <= n-3 or d2<= n-3: answer -=1 return answer colors = [1,2,3,4] print(solve(colors))

  ইনপুট

  [1,2,3,4] 

  আউটপুট

  11