นับการเรียงสับเปลี่ยนสระใน C++

ให้ตัวเลข n นับจำนวนสตริงความยาว n ที่สร้างจากสระ a,e,i,o,u ตามกติกา: a ต้องตามด้วย e, e ตามด้วย a หรือ i, i ไม่ตามด้วย i, o ตามด้วย i หรือ u, u ตามด้วย a คำตอบอาจใหญ่ ใช้โมดูลอ 10^9+7

เช่น n=2 เอาต์พุต=10 สตริงที่เป็นไปได้: ae, ea, ei, ia, ie, io, iu, oi, ou, ua

วิธีแก้ − ใช้ Matrix Exponentiation คูณเมทริกซ์การเปลี่ยนสถานะ (Transition Matrix)

ตัวอย่าง

#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++) result[i][j] = (i==j)?1: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)); }

นับการเรียงสับเปลี่ยนสระใน C++

ตัวอย่าง

อินพุต

เอาต์พุต