Bit Strings
Count how many binary strings of length n exist, modulo 1e9+7.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Count the number of binary strings of length \(n\), and report the answer modulo \(10^9 + 7\).
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Each position has exactly two choices: \(0\) or \(1\). Therefore the total number of strings is \[ 2^n. \]
The only real work is computing that power under a modulus. Fast exponentiation is the clean standard tool:
repeatedly square the base
multiply it into the answer whenever the current bit of the exponent is \(1\)
That keeps the arithmetic bounded by the modulus and runs in logarithmic time.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(\log n)\)
Memory: \(O(1)\)
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
int main() {
const std::int64_t mod = 1000000007LL;
std::int64_t n;
std::cin >> n;
std::int64_t result = 1;
std::int64_t base = 2;
while (n > 0) {
if (n & 1LL) {
result = (result * base) % mod;
}
base = (base * base) % mod;
n >>= 1LL;
}
std::cout << result << '\n';
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
Even though a simple loop of \(n\) doublings would pass here, binary exponentiation scales better and keeps the implementation standard.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.