ধরি দুটি স্ট্রিং str1 এবং str2 আছে, আমাদের দৈর্ঘ্য L-এর ম্যাজিক্যাল জোড়ার সংখ্যা বের করতে হবে। দুটি স্ট্রিং ম্যাজিক্যাল হব যদি প্রতিটি ইনডেক্স i-তে str1[i] < str2[i] হয়। যেহেতু সংখ্যাটি খুব বড় হতে পারে, তাই মডুলো 10⁹ দিয়ে উত্তর দিতে হবে। স্ট্রিংগুলিতে শুধু ছোট হাতের অক্ষর থাকবে।
অ্যাপ্রোচটি সহজ। L = 1 হলে, str1-এ 'a' থাকলে str2-এ 'b' থেকে 'z' পর্যন্ত ২৫ কম্বিনেশন, পরের ক্যারেক্টারের জন্য ২৪, মোট 25 + 24 + ... + 1 = 325। L = 2 হলে 325²। দৈর্ঘ্য L-এর জন্য 325^L। যদি বড় হয় তবে মডুলো 10⁹ নিয়ে বের করুন।
উদাহরণ কোড
#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 = 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;
}
আউটপুট
Combinations: 105625
