计算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” ，“ 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的数组A：= {{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），请执行-

• 如果i与j相同，则result [i，j]：= 1

• 否则，结果[i，j]：= 0

• 对于初始化j：= 0，当j <5时，更新（将j增加1），执行-

• （将n减1）

• 对于初始化i：= 1，当i <= n时，更新（将i增加1），-

• 结果=结果* A

• 和：= 0

• 对于初始化i：= 0，当i <5时，更新（将i增加1），请执行-

• 总和：=加（结果[i，j]，总和）

• 对于初始化j：= 0，当j <5时，更新（将j增加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++) {
         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