AOI Study Hub

Appearance

Binary Strings ​

Written by Iyed Baassou

Key observation ​

The number of binary strings of length is

Let's try and prove it:

For , there is exactly one binary string of length 0 (the empty string), and , so our claim is true for this value of .

Assume there are binary strings of length . Any binary string of length can be formed by choosing a binary string of length (there are choices by the inductive hypothesis) and appending either 0 or 1 (2 choices). Thus there are binary strings of length .

By induction the statement holds for all .

Subtask 1: ​

So fits in C++ long long type, which means we can easily calculate (1LL << n) % MOD.

Subtask 2: ​

Well is obviously HUGE.

So we need to instead multiply our result by 2 for times using res = (res * 2) % MOD. This runs in O(n) which is feasible for this subtask.

Subtask 3: ​

In order to solve this subtask and get the beautiful 100/100. We need to use Binary Exponentiation. This algorithm calculates in logarithmic time.

Implementation (C++) ​

cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;

ll binexp(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b % 2) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ll n; cin >> n;
    cout << binexp(2, n) << "\n";
}