Dreamoon likes sequences very much. So he created a problem about the sequence that you can’t find in OEIS:
You are given two integers $d, m$, find the number of arrays $a$, satisfying the following constraints:
- The length of $a$ is $n$, $n \ge 1$
- $1 \le a_1 < a_2 < \dots < a_n \le d$
- Define an array $b$ of length $n$ as follows: $b_1 = a_1$, $\forall i > 1, b_i = b_{i – 1} \oplus a_i$, where $\oplus$ is the bitwise exclusive-or (xor). After constructing an array $b$, the constraint $b_1 < b_2 < \dots < b_{n – 1} < b_n$ should hold.
Since the number of possible arrays may be too large, you need to find the answer modulo $m$.Input
The first line contains an integer $t$ ($1 \leq t \leq 100$) denoting the number of test cases in the input.
Each of the next $t$ lines contains two integers $d, m$ ($1 \leq d, m \leq 10^9$).
Note that $m$ is not necessary the prime!Output
For each test case, print the number of arrays $a$, satisfying all given constrains, modulo $m$.Exampleinput
10 1 1000000000 2 999999999 3 99999998 4 9999997 5 999996 6 99995 7 9994 8 993 9 92 10 1
output
1 3 5 11 17 23 29 59 89 0
Solution:
#include <bits/stdc++.h> using namespace std; template <typename T> T inverse(T a, T m) { T u = 0, v = 1; while (a != 0) { T t = m / a; m -= t * a; swap(a, m); u -= t * v; swap(u, v); } assert(m == 1); return u; } template <typename T> class Modular { public: using Type = typename decay<decltype(T::value)>::type; constexpr Modular() : value() {} template <typename U> Modular(const U& x) { value = normalize(x); } template <typename U> static Type normalize(const U& x) { Type v; if (-mod() <= x && x < mod()) v = static_cast<Type>(x); else v = static_cast<Type>(x % mod()); if (v < 0) v += mod(); return v; } const Type& operator()() const { return value; } template <typename U> explicit operator U() const { return static_cast<U>(value); } constexpr static Type mod() { return T::value; } Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; } Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; } template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); } template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); } Modular& operator++() { return *this += 1; } Modular& operator--() { return *this -= 1; } Modular operator++(int) { Modular result(*this); *this += 1; return result; } Modular operator--(int) { Modular result(*this); *this -= 1; return result; } Modular operator-() const { return Modular(-value); } template <typename U = T> typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) { #ifdef _WIN32 uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value); uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m; asm( "divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod()) ); value = m; #else value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value)); #endif return *this; } template <typename U = T> typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) { int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod()); value = normalize(value * rhs.value - q * mod()); return *this; } template <typename U = T> typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) { value = normalize(value * rhs.value); return *this; } Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); } template <typename U> friend const Modular<U>& abs(const Modular<U>& v) { return v; } template <typename U> friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs); template <typename U> friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs); template <typename U> friend std::istream& operator>>(std::istream& stream, Modular<U>& number); private: Type value; }; template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; } template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); } template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; } template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); } template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); } template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); } template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; } template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; } template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; } template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; } template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; } template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; } template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; } template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; } template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; } template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; } template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; } template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; } template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; } template<typename T, typename U> Modular<T> power(const Modular<T>& a, const U& b) { assert(b >= 0); Modular<T> x = a, res = 1; U p = b; while (p > 0) { if (p & 1) res *= x; x *= x; p >>= 1; } return res; } template <typename T> bool IsZero(const Modular<T>& number) { return number() == 0; } template <typename T> string to_string(const Modular<T>& number) { return to_string(number()); } template <typename T> std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) { return stream << number(); } template <typename T> std::istream& operator>>(std::istream& stream, Modular<T>& number) { typename common_type<typename Modular<T>::Type, int64_t>::type x; stream >> x; number.value = Modular<T>::normalize(x); return stream; } using ModType = int; struct VarMod { static ModType value; }; ModType VarMod::value; ModType& md = VarMod::value; using Mint = Modular<VarMod>; int main() { ios::sync_with_stdio(false); cin.tie(0); int tt; cin >> tt; while (tt--) { int d; cin >> d >> md; vector<Mint> a; for (int bit = 0; bit <= 30; bit++) { int from = 1 << bit; int to = min(d, (1 << (bit + 1)) - 1); if (from <= to) { a.push_back(to - from + 1); } } int sz = (int) a.size(); vector<Mint> dp(sz); Mint ans = 0; for (int i = 0; i < sz; i++) { dp[i] = a[i]; for (int j = 0; j < i; j++) { dp[i] += a[i] * dp[j]; } ans += dp[i]; } cout << ans << '\n'; } return 0; }
Related posts:
Two Sets
Wrong Answer on Test 233 (Easy Version)
Sieve of Eratosthenes
LRU
Manacher's Algorithm - Finding all sub-palindromes in $O(N)$
Road to 1600
New Year and Hurry
Little Artem and Random Variable
One-Based Arithmetic
Old Peykan
Rotate Columns (easy version)
Civilization
Clockwork Bomb
Splitting the Uniqueness
Scheduling jobs on one machine
Finding the nearest pair of points
Maximum flow - Push-relabel method improved
Giving Awards
4-point polyline
Grid Sort
Sereja ans Anagrams
Chat Order
Declined Finalists
Students Initiation
Paint the String
New Year and Domino
Fox and Minimal path
Landmarks
Vanya and Lanterns
Flows with demands
Almost Same Distance
Pillars