মনে করুন, একটি ধনাত্মক পূর্ণসংখ্যা n দেওয়া আছে। দৈর্ঘ্য n-এর সকল সম্ভাব্য উপস্থিতি রেকর্ডের মধ্যে কতগুলো পুরস্কারযোগ্য (rewardable) তা বের করতে হবে। উত্তর বড় হলে 10^9+7 দিয়ে মডুলো নিন।
উপস্থিতি রেকর্ডে শুধু তিনটি ক্যারেক্টার থাকতে পারে:
- 'A' — অনুপস্থিত
- 'L' — বিলম্বে
- 'P' — উপস্থিত
একটি রেকর্ড পুরস্কারযোগ্য হবে যদি এতে একটির অধিক 'A' বা দুইটির অধিক সিরিয়াল 'L' না থাকে।
n = 2 হলে, আউটপুট ৮। সম্ভাব্য: [PP, AP, PA, LP, PL, AL, LA, LL], শুধু AA বাদ।
সমাধানের ধাপসমূহ
- add(a,b) ফাংশন মডুলো যোগের জন্য
- p, a, l, ap, al অ্যারে সাইজ n+1
- বেস কেস: n=1 হলে ৩ রিটার্ন
- p[0]=1, p[1]=1, p[2]=3; a[0]=1, a[1]=1, a[2]=2; l[0]=1, l[1]=1, l[2]=3; ap[0]=1, ap[1]=1, ap[2]=2; al[0]=1, al[1]=1, al[2]=2
- i := 3 থেকে n পর্যন্ত:
- p[i] = add(add(p[i-1], a[i-1]), l[i-1])
- l[i] = add(add(p[i-1], p[i-2]), add(a[i-1], a[i-2]))
- a[i] = add(al[i-1], ap[i-1])
- al[i] = add(ap[i-1], ap[i-2])
- ap[i] = add(ap[i-1], al[i-1])
- রিটার্ন add(add(p[n], l[n]), a[n])
উদাহরণ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli m = 1e9 + 7; class Solution { public: lli add(lli a, lli b){ return ( (a % m) + (b % m) ) % m; } int checkRecord(int n) { vector <int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1); if(n == 1)return 3; p[0] = 1; p[1] = 1; p[2] = 3; a[0] = 1; a[1] = 1; a[2] = 2; l[0] = 1; l[1] = 1; l[2] = 3; ap[0] = 1; ap[1] = 1; ap[2] = 2; al[0] = 1; al[1] = 1; al[2] = 2; for(int i = 3; i <= n; i++){ p[i] = add(add(p[i-1], a[i-1]), l[i-1]); l[i] = add(add(p[i-1], p[i-2]),add(a[i-1] , a[i-2])); a[i] = add(al[i-1], ap[i-1]); al[i] = add(ap[i-1], ap[i-2]); ap[i] = add(ap[i-1], al[i-1]); } return add(add(p[n], l[n]), a[n]); } }; main(){ Solution ob; cout << (ob.checkRecord(3)); }
ইনপুট
3
আউটপুট
19
