计算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((amodm)+(bmodm))modm
定义一个函数mul()
,这将需要a,b,
return((amodm)*(bmodm))modm
定义一个函数solve()
,将花费n,
定义一个大小为5x5的数组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}}
定义大小为5x5的数组结果。
对于初始化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