Đếm số chuỗi nhị phân độ dài N trong C++

Cho số num. Đếm số chuỗi nhị phân độ dài num (chỉ chứa 0 và 1).

Ví dụ

num = 3 → 8 chuỗi: 000, 111, 001, 101, 100, 110, 011, 010

num = 2 → 4 chuỗi: 00, 11, 01, 10

Phương pháp

Số chuỗi nhị phân độ dài n là 2ⁿ. Tính 2ⁿ mod (10⁹+7) bằng lũy thừa nhanh (binary exponentiation).

Ví dụ minh họa (C++)

#include <iostream>
using namespace std;

#define ll long long
#define mod (ll)(1e9 + 7)

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;
}

Đầu ra

count is: 8