cses

commit 19bb82f44e8da0ab854f93248a8fe72d430b46e4
parent 146f58d5d91133e43045df719b3f0ae7ad1266f0
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 13 Feb 2025 15:11:28 -0700

1617. bit strings

Diffstat:
A
introductory_problems/bit_strings.cpp
 | 
21
+++++++++++++++++++++
M
introductory_problems/readme.md
 | 
7
+++++++

2 files changed, 28 insertions(+), 0 deletions(-)
diff --git a/introductory_problems/bit_strings.cpp b/introductory_problems/bit_strings.cpp
@@ -0,0 +1,21 @@
+// 1617. Bit Strings
+#include <bits/stdc++.h>
+
+const int mod = 1e9 + 7;
+
+long long fast_pow2(int x) {
+  long long res = 1, y = 2;
+  while (x) {
+    if (x & 1)
+      res = (res * y) % mod;
+    y = (y * y) % mod;
+    x >>= 1;
+  }
+  return res;
+}
+
+int main() {
+  static int n;
+  scanf("%d", &n);
+  printf("%lld\n", fast_pow2(n));
+}
diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md
@@ -55,3 +55,10 @@ Your task is to divide the numbers `1, 2, ..., n` into two sets of equal sum.
 **Input**: The only input line contains an integer `n`. (Example: 7)
 
 **Output**: Print "YES", if the division is possible, and "NO" otherwise. After this, print if the division is possible, print an example of how to create the sets.
+
+### Bit Strings
+Your task is to calculate the number of bit strings of length `n`. For example, if `n = 3`, the correct answer is 8, because the possible bit strings are `000`, `001`, `010`, `011`, `100`, `101`, `110`, and `111`.
+
+**Input**: The only input line has an integer `n`. (Example: 3)
+
+**Output**: Print the result modulo 10E9 + 7. (Example: 8)