Đếm số nguyên âm hoán vị trong C ++

Giả sử chúng ta có một số n, chúng ta phải đếm xem có bao nhiêu chuỗi có độ dài n có thể được tạo thành bằng cách sử dụng các quy tắc này - Mỗi ký tự là một nguyên âm chữ thường Mỗi nguyên âm 'a' chỉ có thể được theo sau bởi một 'e'. Mỗi nguyên âm 'e' chỉ có thể được theo sau bởi một 'a' hoặc 'i'. Mỗi nguyên âm 'i' không được theo sau bởi một 'i' khác. Mỗi nguyên âm 'o' chỉ có thể được theo sau bởi một 'i' hoặc 'u'. Mỗi nguyên âm 'u' chỉ có thể được theo sau bởi một 'a'. Câu trả lời có thể quá lớn, vì vậy chúng tôi sẽ tìm câu trả lời theo mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là 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 vấn đề này, chúng tôi sẽ làm theo các bước sau -

m =1 ^ 9 + 7
Xác định một hàm add (), điều này sẽ lấy a, b,
return ((a mod m) + (b mod m)) mod m
Xác định một hàm mul (), điều này sẽ nhận a, b,
return ((a mod m) * (b mod m)) mod m
Xác định một hàm giải quyết (), điều này sẽ mất n,
Xác định một mảng A có 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}}
Xác định kết quả mảng có kích thước:5 x 5.
để khởi tạo i:=0, khi tôi <5, hãy cập nhật (tăng i lên 1), thực hiện -
- để 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 tôi giống với j thì kết quả [i, j]:=1
  - Nếu không, kết quả [i, j]:=0
(giảm n đi 1)
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- results =kết quả * A
tổng:=0
để khởi tạo i:=0, khi tôi <5, hãy cập nhật (tăng i lên 1), thực hiện -
- để 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ả lại số tiền

Hãy cùng chúng tôi xem cách 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));
}

Đếm số nguyên âm hoán vị trong C ++

Ví dụ

Đầu vào

Đầu ra