นับการเปลี่ยนแปลงของสระใน 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".

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม =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

• กำหนดขนาดอาร์เรย์ A: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}}

• กำหนดผลลัพธ์อาร์เรย์ของขนาด:5 x 5

• สำหรับการเริ่มต้น i :=0 เมื่อ i <5 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <5 อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

    • ถ้าฉันเหมือนกับ j แล้วผลลัพธ์[i, j] :=1

    • มิฉะนั้น ผลลัพธ์[i, j] :=0

• (ลดลง n โดย 1)

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ผลลัพธ์ =ผลลัพธ์ * A

• ผลรวม :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <5 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <5 อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

    • ผลรวม :=เพิ่ม (ผลลัพธ์[i, j], ผลรวม)

• ผลตอบแทนรวม

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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