C++-এ স্বরবর্ণ পারমুটেশন গণনা (Count Vowels Permutation)

একটি সংখ্যা n দেওয়া আছে। নিচের নিয়ম মেনে দৈর্ঘ্য n এর কতগুলো স্ট্রিং বানানো যায় তা বের করতে হবে:

প্রতিটি ক্যারেক্টার ছোট হাতের স্বরবর্ণ (a, e, i, o, u)।
a এর পর শুধু e আসতে পারে।
e এর পর শুধু a বা i আসতে পারে।
i এর পর i বাদে যেকোনো স্বরবর্ণ আসতে পারে।
o এর পর শুধু i বা u আসতে পারে।
u এর পর শুধু a আসতে পারে।

উত্তর বড় হতে পারে, তাই মডুলো 10^9 + 7।

উদাহরণ

ইনপুট: 2 → আউটপুট: 10

সম্ভাব্য স্ট্রিং: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"

সমাধানের ধাপসমূহ

ম্যাট্রিক্স এক্সপোনেনশিয়েশন (Matrix Exponentiation) ব্যবহার করুন।
ট্রানজিশন ম্যাট্রিক্স A[5][5] তৈরি করুন যেখানে নিয়ম অনুযায়ী সংযোগ আছে।
A^(n-1) ক্যালকুলেট করুন।
সকল এন্ট্রির যোগফলই উত্তর।

প্রোগ্রাম উদাহরণ

#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++) result[i][i] = 1;
        
        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(sum, result[i][j]);
        return sum;
    }
    
    int countVowelPermutation(int n) {
        return solve(n);
    }
};

int main() {
    Solution ob;
    cout << (ob.countVowelPermutation(2));
}