cses

solution to cses exercise problems
git clone git://git.superpozycja.net/cses
Log | Files | Refs | README

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 }