C++ এ স্বরবর্ণের ক্রমাগত গণনা করুন

ধরুন আমাদের একটি সংখ্যা n আছে, এই নিয়মগুলি ব্যবহার করে n দৈর্ঘ্যের কতগুলি স্ট্রিং তৈরি করা যেতে পারে তা আমাদের গণনা করতে হবে − প্রতিটি অক্ষর একটি ছোট হাতের স্বরবর্ণ প্রতিটি স্বর 'a' শুধুমাত্র একটি 'e' দ্বারা অনুসরণ করা যেতে পারে। প্রতিটি স্বর 'ই' শুধুমাত্র একটি 'a' বা 'i' দ্বারা অনুসরণ করা যেতে পারে। প্রতিটি স্বরবর্ণ 'i' অন্য 'i' দ্বারা অনুসরণ নাও হতে পারে। প্রতিটি স্বরবর্ণ 'o' শুধুমাত্র একটি 'i' বা 'u' দ্বারা অনুসরণ করা যেতে পারে। প্রতিটি স্বর 'উ' শুধুমাত্র একটি 'এ' দ্বারা অনুসরণ করা যেতে পারে। উত্তরটি অনেক বড় হতে পারে, তাই আমরা উত্তর মডিউল 10^9 + 7 খুঁজে পাব।

সুতরাং, যদি ইনপুট 2 এর মত হয়, তাহলে আউটপুট হবে 10, কারণ সম্ভাব্য সমস্ত স্ট্রিং হল "ae", "ea", "ei", "ia", "ie", "io", "iu" , "oi", "ou", "ua"।

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

m =1^9 + 7
একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে
ফিরুন ((a mod m) + (b mod m)) mod m
একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে
(a mod m) * (b mod m)) mod m
ফেরত দিন
একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি n,
লাগবে
আকারের একটি অ্যারে সংজ্ঞায়িত করুন:5 x 5 :={{0,1,0,0,0},{1,0,1,0,0},{1,1,0,1,1},{ 0,0,1,0,1},{1,0,0,0,0}}
আকারের একটি অ্যারের ফলাফল নির্ধারণ করুন:5 x 5।
আরম্ভ করার জন্য i :=0, যখন i <5, আপডেট করুন (i 1 দ্বারা বাড়ান), −
- j আরম্ভ করার জন্য :=0, যখন j <5, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), −
  করুন
  - যদি i j এর মত হয়, তাহলে ফলাফল[i, j] :=1
  - অন্যথায়, ফলাফল[i, j] :=0
(1 দ্বারা n হ্রাস করুন)
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
- ফলাফল =ফলাফল * A
যোগফল :=0
আরম্ভ করার জন্য i :=0, যখন i <5, আপডেট করুন (i 1 দ্বারা বাড়ান), −
- j আরম্ভ করার জন্য :=0, যখন j <5, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), −
  করুন
  - যোগফল :=যোগ(ফলাফল[i, j], যোগফল)
ফেরত যোগফল

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9+7;
lli add(lli a, lli b){
   return ((a%m) + (b%m))%m;
}
lli mul(lli a, lli b){
   return ((a%m) * (b%m))%m;
}
class Solution {
   public:
   void multiply(lli A[5][5], lli B[5][5]){
      lli C[5][5];
      for(lli i =0;i<5;i++){
         for(lli j=0;j<5;j++){
            lli temp =0;
            for(lli k =0;k<5;k++){
               temp = add(temp,mul(A[i][k],B[k][j]));
            }
            C[i][j] = temp;
         }
      }
      for(lli i =0;i<5;i++){
         for(lli j =0;j<5;j++){
            A[i][j] = C[i][j];
         }
      }
   }
   lli solve(lli n){
      lli A[5][5] = { { 0, 1, 0, 0, 0 }, { 1, 0, 1, 0, 0 }, { 1, 1,
      0, 1, 1 }, { 0, 0, 1, 0, 1 }, { 1, 0, 0, 0, 0 } };
      lli result[5][5];
      for (lli i = 0; i < 5; i++) {
         for (lli j = 0; j < 5; j++) {
            if (i == j)
               result[i][j] = 1;
            else
               result[i][j] = 0;
         }
      }
      n--;
      for (int i = 1; i <= n; i++)
      multiply(result, A);
      lli sum = 0;
      for (lli i = 0; i < 5; i++) {
         for (lli j = 0; j < 5; j++) {
            sum = add(result[i][j], sum);
         }
      }
      return sum;
   }
   int countVowelPermutation(int n) {
      return solve(n);
   }
};
main(){
   Solution ob;
   cout << (ob.countVowelPermutation(2));
}