C++에서 모음 순열 카운트

<시간/>

하나의 숫자 n이 있다고 가정하고 이 규칙을 사용하여 길이가 n인 문자열을 몇 개나 만들 수 있는지 계산해야 합니다. - 각 문자는 소문자 모음입니다. 각 모음 'a' 뒤에는 'e'만 올 수 있습니다. 각 모음 'e' 뒤에는 'a' 또는 'i'만 올 수 있습니다. 각 모음 'i' 뒤에는 다른 'i'가 올 수 없습니다. 각 모음 'o' 뒤에는 'i' 또는 'u'만 올 수 있습니다. 각 모음 'u' 뒤에는 'a'만 올 수 있습니다. 답이 너무 클 수 있으므로 모듈로 10^9 + 7로 답을 찾습니다.

따라서 입력이 2와 같으면 출력은 10이 됩니다. 가능한 모든 문자열이 "ae", "ea", "ei", "ia", "ie", "io", "iu"이기 때문입니다. , "오이", "우", "우아".

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m =1^9 + 7
add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
mul() 함수를 정의하면, b,
return ((a mod m) * (b mod m)) mod m
solve() 함수를 정의하면 n이 필요합니다.
다음과 같은 크기의 배열 A를 정의합니다. 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 크기의 배열 결과를 정의합니다.
initialize i :=0의 경우, i <5일 때 업데이트(i 1만큼 증가), 수행 -
- j를 초기화하기 위해 :=0, j <5일 때 업데이트(j를 1만큼 증가), −
  - i가 j와 같으면 result[i, j] :=1
  - 그렇지 않으면 결과[i, j] :=0
(n을 1씩 감소)
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
- 결과 =결과 * A
합계 :=0
initialize 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));
}