C++ এ ছাত্র উপস্থিতির রেকর্ড II

ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা n আছে, আমাদের দৈর্ঘ্য n সহ সম্ভাব্য সমস্ত উপস্থিতি রেকর্ডের সংখ্যা খুঁজে বের করতে হবে, যা পুরস্কারযোগ্য হিসাবে বিবেচিত হবে। যেহেতু উত্তরটি অনেক বড় হতে পারে, আমরা মোড 109 + 7 ব্যবহার করে এটি ফেরত দেব।

শিক্ষার্থীদের উপস্থিতি রেকর্ডে স্ট্রিংটিতে শুধুমাত্র নিম্নলিখিত তিনটি অক্ষর থাকতে পারে −

'A' মানে অনুপস্থিত।
'L' মানে দেরী।
'P' মানে বর্তমান।

একটি উপস্থিতি পুরস্কারযোগ্য হিসাবে বিবেচিত হয় যদি এতে একাধিক 'A' (অনুপস্থিত) বা দুটির বেশি অবিচ্ছিন্ন 'L' (দেরিতে) না থাকে। তাই আমাদের সর্বোচ্চ পয়েন্ট খুঁজে বের করতে হবে।

যদি ইনপুট 2 এর মত হয়, তাহলে আউটপুট হবে 8, যেহেতু আমরা পুরস্কৃত হতে পারে এমন 8টি সম্ভাব্য উপায় তৈরি করতে পারি, এইগুলি হল [PP, AP, PA, LP, PL, AL, LA, LL], শুধুমাত্র AA হবে না সেখানে থাকুন।

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

একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,
- রিটার্ন ((a mod m) + (b mod m)) mod m
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন,
n + 1 আকারের একটি অ্যারে p, n + 1 আকারের অ্যারে, n + 1 আকারের একটি অ্যারে, n + 1 আকারের একটি অ্যারে ap এবং n + 1 আকারের একটি অ্যারে al সংজ্ঞায়িত করুন
যদি 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, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করুন −
- 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(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));
}