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:
Integration by Simpson's formula
Yash And Trees
Kind Anton
Ilya and a Colorful Walk
PolandBall and Gifts
Matching Names
Edge Weight Assignment
New Year Tree
Lingua Romana
Bonus Distribution
Traveling Around the Golden Ring of Berland
Chip Game
Topological Sorting
Travel Cards
PolandBall and Hypothesis
Optimal Polygon Perimeter
Operations on polynomials and series
Lowest Common Ancestor - Tarjan's off-line algorithm
Useful Decomposition
Meaningless Operations
Kate and imperfection
Aztec Catacombs
Intellectual Inquiry
New Year Present
Finding Bridges Online
Chinese Remainder Theorem
Worms
Prefix Enlightenment
Movie Fan
Dima and Game
Dream Team
Table Compression