समस्या विवरण
एक संख्या n दी गई है। लंबाई n के ऐसे स्ट्रिंग्स की गिनती करनी है जो निम्न नियमों का पालन करते हैं:
- प्रत्येक अक्षर लोअरकेस स्वर (a, e, i, o, u) है।
- 'a' के बाद केवल 'e' आ सकता है।
- 'e' के बाद केवल 'a' या 'i' आ सकता है।
- 'i' के बाद 'i' नहीं आ सकता (अन्य सभी स्वर आ सकते हैं)।
- 'o' के बाद केवल 'i' या 'u' आ सकता है।
- 'u' के बाद केवल 'a' आ सकता है।
उत्तर मॉड्यूलो 10^9 + 7 में लौटाएं।
उदाहरण
इनपुट: n = 2
आउटपुट: 10
संभावित स्ट्रिंग्स: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"
समाधान दृष्टिकोण (मैट्रिक्स एक्सपोनेंशिएशन / DP)
संक्रमण मैट्रिक्स (Transition Matrix) 5×5 बनाएं जहां M[i][j] = 1 यदि स्वर i के बाद स्वर j आ सकता है।
तब M^(n-1) की सभी प्रविष्टियों का योग उत्तर है।
स्वर क्रम: a=0, e=1, i=2, o=3, u=4
M = {{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}}
कार्यकारी प्रोग्राम
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli MOD = 1e9+7;
lli add(lli a, lli b) { return (a%MOD + b%MOD)%MOD; }
lli mul(lli a, lli b) { return (a%MOD * b%MOD)%MOD; }
class Solution {
public:
void multiply(lli A[5][5], lli B[5][5]) {
lli C[5][5] = {};
for (int i=0;i<5;i++)
for (int j=0;j<5;j++)
for (int k=0;k<5;k++)
C[i][j] = add(C[i][j], mul(A[i][k], B[k][j]));
for (int i=0;i<5;i++)
for (int 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 res[5][5] = {};
for (int i=0;i<5;i++) res[i][i] = 1; // पहचान मैट्रिक्स
n--;
for (int i=1; i<=n; i++) multiply(res, A);
lli sum = 0;
for (int i=0;i<5;i++)
for (int j=0;j<5;j++)
sum = add(sum, res[i][j]);
return sum;
}
int countVowelPermutation(int n) { return solve(n); }
};
int main() {
Solution ob;
cout << ob.countVowelPermutation(2);
return 0;
}
आउटपुट
10