C++で母音の順列を数える

数nが1つあるとすると、これらの規則を使用して、長さ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」であるためです。 、"oi"、 "ou"、"ua"。

これを解決するには、次の手順に従います-

• m =1 ^ 9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod m）*（b mod m））mod m

• 関数solve（）を定義します。これにはnが必要です。

• サイズ：5 x 5：={{0,1,0,0,0}、{1,0,1,0,0}、{1,1,0,1,1}、{の配列Aを定義します0,0,1,0,1}、{1,0,0,0,0}}

• サイズが5x5の配列結果を定義します。

• 初期化i：=0の場合、i <5の場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j <5の場合、更新（jを1増やします）、実行-

    • iがjと同じである場合、result [i、j]：=1

    • それ以外の場合、result [i、j]：=0

• （nを1減らします）

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • 結果=結果*A

• 合計：=0

• 初期化i：=0の場合、i <5の場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j <5の場合、更新（jを1増やします）、実行-

    • sum：=add（result [i、j]、sum）

• 合計を返す

理解を深めるために、次の実装を見てみましょう-

例

#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));
}

入力

2

出力

10