আমাদের একটি সংখ্যা num দেওয়া আছে। কাজ হল দৈর্ঘ্য num-এর শুধু ০ এবং ১ দিয়ে গঠিত বাইনারি স্ট্রিংয়ের মোট সংখ্যা গণনা করা।
বাইনারি নাম্বার সিস্টেম ডিজিটাল সিস্টেমে সবচেয়ে জনপ্রিয়। এখানে শুধু ০ এবং ১ دوটি সিম্বল থাকে। দৈর্ঘ্য N-এর বাইনারি স্ট্রিংয়ের মোট সম্ভাব্য কোম্বিনেশন = 2^N।
উদাহরণ:
ইনপুট: num = 3 → আউটপুট: count is 8 (000, 111, 001, 101, 100, 110, 011, 010)
ইনপুট: num = 2 → আউটপুট: count is 4 (00, 11, 01, 10)
অ্যালগরিদম
ইনপুট নিন long long num-এ (বড় সংখ্যা হয়তে পারে)
Mod = 1e9+7 সেট করুন
Fast Exponentiation (Binary Exponentiation) ব্যবহার করে (2^num) % mod বের করুন
ফলাফল রিটার্ন করুন
প্রোগ্রাম
#include <iostream>
using namespace std;
#define ll long long
#define mod (ll)(1e9 + 7)
// O(log y)-এ (x^y)%p বের করার ফাংশন
ll power(ll x, ll y, ll p) {
ll result = 1;
x = x % p;
while (y > 0) {
if (y & 1) result = (result * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return result;
}
// বাইনারি স্ট্রিংয়ের সংখ্যা গণনা
ll countbstring(ll num) {
return power(2, num, mod);
}
int main() {
ll num = 3;
cout << "count is: " << countbstring(num);
return 0;
}
আউটপুট
count is: 8
