假设我们有一个数字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