cses

commit 1b3a5b30f681cae015f799c9ef3800c7621d885b
parent ce65298723ac6b69799e496368c535fb130251ee
Author: superpozycja <anna@superpozycja.net>
Date:   Thu, 24 Oct 2024 00:05:07 +0200

solve bit strings (like a c chad)

Diffstat:
A
intro/bit_strings.cpp
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 49 insertions(+), 0 deletions(-)
diff --git a/intro/bit_strings.cpp b/intro/bit_strings.cpp
@@ -0,0 +1,49 @@
+#include <bits/stdc++.h>
+
+using namespace std;
+
+using ui = unsigned int;
+using l = long;
+using ul = unsigned long;
+using ll = long long;
+using ull = unsigned long long;
+
+using vi = vector<int>;
+using vui = vector<ui>;
+using vl = vector<l>;
+using vul = vector<ul>;
+using vll = vector<ll>;
+using vull = vector<ull>;
+
+uint32_t reverse(uint32_t x)
+{
+    x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1);
+    x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2);
+    x = ((x >> 4) & 0x0f0f0f0fu) | ((x & 0x0f0f0f0fu) << 4);
+    x = ((x >> 8) & 0x00ff00ffu) | ((x & 0x00ff00ffu) << 8);
+    x = ((x >> 16) & 0xffffu) | ((x & 0xffffu) << 16);
+    return x;
+}
+
+void solve()
+{
+	uint32_t n;
+	long long res = 1;
+	cin >> n;
+	int z = 32 - __builtin_clz(n);
+	n = reverse(n) >> (32 - z);
+	while (z--) {
+		res *= (res % (1000000007));
+		if ((n&1) == 1) {
+			res *= 2 % (1000000007);
+		}
+		res %= 1000000007;
+		n >>= 1;
+	}
+	cout << res << "\n";
+}
+
+int main()
+{
+	solve();
+}