मान लीजिए हमारे पास दो स्ट्रिंग्स str1 और str2 हैं, हमें लंबाई L के जादुई जोड़ों की संख्या ढूंढनी है। दो स्ट्रिंग्स जादुई होंगी यदि प्रत्येक इंडेक्स i के लिए, str1[i] < str2[i] हो। हमें जोड़ों की संख्या गिननी है चूंकि संख्या बहुत बड़ी है, तो उत्तर को मॉड्यूलो 10⁹ का उपयोग करके लौटाएं। स्ट्रिंग्स केवल लोअरकेस अक्षर रखेंगी।
दृष्टिकोण सरल है। जैसा कि हम देख सकते हैं, यदि लंबाई L=1 है, और इंडेक्स i=1 पर 'a' है str1 में, तो str2 के इंडेक्स i=1 पर 'b' से 'z' तक होगा, इसलिए 25 संयोजन, अगले वर्ण के लिए 24 संयोजन होंगे, तो यह 25 + 24 + ... + 1 = 325 होगा। अब L=2 के लिए, यह 325² होगा। लंबाई L के लिए, यह 325ᴸ होगा। यदि यह बहुत बड़ा है, तो मॉड्यूलस 10⁹ ज्ञात करें।
C++ उदाहरण
#include <iostream>
#include <cmath>
using namespace std;
int power(int a, unsigned int b, int mod) {
int res = 1;
a = a % mod;
while (b > 0) {
if (b & 1) res = (res * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return res;
}
int main() {
int L = 2, P = pow(10, 9);
int res = power(325, L, P);
cout << "Combinations: " << res << endl;
return 0;
}
आउटपुट
Combinations: 105625