資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
