একটি সংখ্যা n দেওয়া আছে। 3 x n আকারের বক্সকে 1 x 2 ডোমিনো দিয়ে কতভাবে ভরা যায় সেটি বের করতে হবে। ডোমিনো ঘুরিয়ে ব্যবহার করা যাবে। উত্তর বড় হলে 10^9+7 দিয়ে মড করুন।
উদাহরণস্বরূপ, n = 4 হলে আউটপুট ১১।
সমাধানের পদ্ধতি (রিকারেন্স রিলেশন)
n বিজোড় হলে ০ (কারণ ৩×বিজোড় এলিমেন্ট ২×১ ডোমিনো দিয়ে কভার করা যায় না)। জোড় n এর জন্য রিকারেন্স:
cs= কমপ্লিট টাইলিং সংখ্যা,os= অ半-টাইলিং (একদিকের প্রট্রুশন) সংখ্যা।cs_new = 3*cs + os,os_new = 2*cs + os।- ইনিশিয়াল:
cs=1, os=0(n=0)। i = 2, 4, ..., nপর্যন্ত লুপ।
পাইথন কোড উদাহরণ
class Solution:
def solve(self, n):
m = 10**9 + 7
if n % 2 == 1:
return 0
cs = 1
os = 0
for i in range(2, n+1, 2):
cs, os = (3*cs + os, 2*cs + os)
return cs % m
ob = Solution()
n = 4
print(ob.solve(n))ইনপুট
4
আউটপুট
11
