bit_strings.cpp (965B)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 using ui = unsigned int; 6 using l = long; 7 using ul = unsigned long; 8 using ll = long long; 9 using ull = unsigned long long; 10 11 using vi = vector<int>; 12 using vui = vector<ui>; 13 using vl = vector<l>; 14 using vul = vector<ul>; 15 using vll = vector<ll>; 16 using vull = vector<ull>; 17 18 uint32_t reverse(uint32_t x) 19 { 20 x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1); 21 x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2); 22 x = ((x >> 4) & 0x0f0f0f0fu) | ((x & 0x0f0f0f0fu) << 4); 23 x = ((x >> 8) & 0x00ff00ffu) | ((x & 0x00ff00ffu) << 8); 24 x = ((x >> 16) & 0xffffu) | ((x & 0xffffu) << 16); 25 return x; 26 } 27 28 void solve() 29 { 30 uint32_t n; 31 long long res = 1; 32 cin >> n; 33 int z = 32 - __builtin_clz(n); 34 n = reverse(n) >> (32 - z); 35 while (z--) { 36 res *= (res % (1000000007)); 37 if ((n&1) == 1) { 38 res *= 2 % (1000000007); 39 } 40 res %= 1000000007; 41 n >>= 1; 42 } 43 cout << res << "\n"; 44 } 45 46 int main() 47 { 48 solve(); 49 }