Giả sử chúng ta có một số n, chúng ta phải đếm có bao nhiêu chuỗi độ dài n có thể được tạo thành theo các quy tắc sau − Mỗi ký tự là một nguyên âm thường. Mỗi nguyên âm 'a' chỉ có thể được theo sau bởi 'e'. Mỗi nguyên âm 'e' chỉ có thể được theo sau bởi 'a' hoặc 'i'. Mỗi nguyên âm 'i' không thể được theo sau bởi 'i' khác. Mỗi nguyên âm 'o' chỉ có thể được theo sau bởi 'i' hoặc 'u'. Mỗi nguyên âm 'u' chỉ có thể được theo sau bởi 'a'. Câu trả lời có thể quá lớn, nên chúng ta sẽ tìm câu trả lời modulo 10^9 + 7.
Vì vậy, nếu đầu vào giống như 2, thì đầu ra sẽ là 10, điều này là do tất cả các chuỗi có thể là "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua".
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
m = 1^9 + 7
Định nghĩa hàm add(), nhận a, b,
trả về ((a mod m) + (b mod m)) mod m
Định nghĩa hàm mul(), nhận a, b,
trả về ((a mod m) * (b mod m)) mod m
Định nghĩa hàm solve(), nhận n,
Định nghĩa mảng A kích thước: 5 x 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}}
Định nghĩa mảng result kích thước: 5 x 5.
for khởi tạo i := 0, khi i < 5, cập nhật (tăng i lên 1), thực hiện −
for khởi tạo j := 0, khi j < 5, cập nhật (tăng j lên 1), thực hiện −
nếu i bằng j, thì, result[i, j] := 1
Ngược lại, result[i, j] := 0
(giảm n xuống 1)
for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), thực hiện −
results = result * A
sum := 0
for khởi tạo i := 0, khi i < 5, cập nhật (tăng i lên 1), thực hiện −
for khởi tạo j := 0, khi j < 5, cập nhật (tăng j lên 1), thực hiện −
sum := add(result[i, j], sum)
trả về sum
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#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)); } Đầu vào
2
Đầu ra
10