数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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，
返回 ((a mod m) + (b mod m)) mod m
定义一个函数 mul()，它将接收 a、b，
返回 ((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 的数组 result。
初始化 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），执行：
results = result * A
sum := 0
初始化 i := 0，当 i < 5 时，更新（i 加 1），执行：
初始化 j := 0，当 j < 5 时，更新（j 加 1），执行：
sum := add(result[i, j], sum)
返回 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
216 次查看
