```

```

Iterate on the leftmost set bit, and count how many valid integers have that bit as their leftmost set bit.

Read hint first.

We are iterating over the bits from 0 to (x — 1). Let's say, we are at bit b. We want to count how many valid integers have msb at b.

We can fill bits from 0 to b — 1. No. of available bits = b. If b is even, this bit can's be msb for a valid integer. Else, no. of set bits remaining to be filled = b / 2. We can choose the positions for set bits by b C (b/2).

For the bit x, there is only one number $$$2^x$$$. If x is 1, this is a valid integer.

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
#define pb push_back

const ll INF = 1e18;
const int maxv = 1e6 + 3;
const ll mod = 1e9 + 7;

vector<ll> fa, ifa;

ll pw(ll b, ll e){
    ll a = 1;
    while(e){
        if(e & 1) a = a * b % mod;
        b = b * b % mod;
        e >>= 1;
    }
    return a;
}

ll mmi(ll x){
    return pw(x, mod - 2);
}

void prec(){
    fa.resize(maxv + 1);
    fa[0] = 1;
    for(int i = 1; i <= maxv; i++) fa[i] = fa[i - 1] * i % mod;
    ifa.resize(maxv + 1);
    ifa[maxv] = mmi(fa[maxv]);
    for(int i = maxv - 1; i >= 0; i--) ifa[i] = ifa[i + 1] * (i + 1) % mod;
}

ll ncr(int n, int r){
    return fa[n] * ifa[r] % mod * ifa[n - r] % mod;
}

ll solve()
{
    int n;
    cin >> n;

    if(n < 0 || n > 1e6) return -1;

    ll ans = 0;
    for(int i = 2; i <= n; i += 2){
        int j = i / 2;
        ans = (ans + ncr(2 * j - 1, j)) % mod;
    }
    if(n == 1) ans = (ans + 1) % mod;
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    prec();
    int t = 1;
    while(t--)
    {
        ll x = solve();
        cout << x << "\n";
    }
    return 0;
}

Try fixing the first two elements and generate the sequence using the rule $$$a_i \oplus a_{i+1} = a_{i+2}$$$.

We are given that:

Fix the first two elements $$$a_1 = x$$$ and $$$a_2 = y$$$.

Then:

So the sequence becomes:

Hence, the sequence is periodic with period $$$3$$$.

Therefore: - The array can have only $$$3$$$ distinct values. - These values must be $$$x$$$, $$$y$$$, and $$$x \oplus y$$$.

So, if the number of distinct elements is not $$$3$$$, the answer is $$$\textbf{NO}$$$.

Now let the frequencies of these three values be $$$f_1, f_2, f_3$$$.

Since the sequence repeats every $$$3$$$ positions, the frequencies must be balanced:

If this condition holds, we can arrange elements in cyclic order and the answer is $$$\textbf{YES}$$$, otherwise $$$\textbf{NO}$$$.

$$$\textbf{Complexity}$$$: $$$O(n \log n)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;
        map<int,int> mp;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            mp[x]++;
        }
        
        if(mp.size() != 3){
            cout << "NO\n";
            continue;
        }
        int mx = 0, mn = 1e9;
        for(auto it : mp){
            mx = max(mx, it.second);
            mn = min(mn, it.second);
        }
        
        cout << (mx - mn <= 1 ? "YES\n" : "NO\n");
    }
}

Use the identity $$$a + b = (a \oplus b) + 2(a \text{ AND } b)$$$.

Think about when addition and XOR differ — it happens due to carries.

Since modulo is $$$2^m$$$, only the lowest $$$m$$$ bits matter. Try avoiding carries in the first $$$m-1$$$ bits.

We are given two expressions

and need to find when they are equal.

We start with the identity

Substituting, the condition becomes

which simplifies to

or

$$$\textbf{Analysis on the above equation}$$$

Since we are working modulo $$$2^{m-1}$$$, this means that the lowest $$$m-1$$$ bits of $$$(a \text{ AND } b)$$$ must all be zero.

In binary terms, the $$$i$$$-th bit of $$$(a \text{ AND } b)$$$ is $$$1$$$ if and only if both $$$a_i = 1$$$ and $$$b_i = 1$$$. Therefore, for every bit position $$$i \lt m-1$$$, we must not have both bits equal to $$$1$$$ simultaneously.

This is equivalent to saying that no carry should occur in the first $$$m-1$$$ bits during addition, since a carry at bit $$$i$$$ happens exactly when $$$a_i = 1$$$ and $$$b_i = 1$$$.

Hence, the condition can be rewritten as

Now let $$$A = 2^x$$$ and $$$B = 2^y$$$. Then $$$a$$$ has at most $$$x$$$ bits and $$$b$$$ has at most $$$y$$$ bits. We only care about bits from $$$0$$$ to $$$m-2$$$, and only where both numbers actually have bits. So the number of relevant bit positions is

At each such bit, the pair $$$(a_i, b_i)$$$ has 4 equally likely outcomes, out of which 3 are valid (all except $$$(1,1)$$$). Since bits are independent, the probability that all these positions avoid a carry is

Thus the required probability is

and we compute

The solution runs in $$$O(\log MOD)$$$ per test case using fast exponentiation.

#include <bits/stdc++.h>
using namespace std;


#define int long long


const int MOD = 1e9 + 7;

int binexp(int a,int b) {
    int ans = 1;
    while (b) {
        if (b & 1){
          ans *= a;
          ans %= MOD;
        }
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return ans;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int A, B, M;
        cin >> A >> B >> M;

        int x = log2(A); 
        int y = log2(B);
        int m = log2(M);

        int C = max(0ll, min({x, y, m - 1}));

        int p = binexp(3, C);
        int q = binexp(4, C);

        int ans = (p * binexp(q, MOD - 2)) % MOD;

        cout << ans << "\n";
    }

    return 0;
}

In a binary array, what does a non-decreasing subsequence look like? Try to describe its structure.

Fix a starting index and think in terms of taking some $$${0s}$$$ first and then $$${1s}$$$. Can you express the length using counts of $$${0s}$$$ and $$${1s}$$$ in a segment?

Try maximizing $$$(\text{number of 0s} - \text{number of 1s})$$$ over a cyclic segment. Can you reduce this to a known problem?

A non-decreasing subsequence in a binary array must be of the form

Since the array is cyclic, we can choose any starting point and traverse once. This splits the traversal into a segment $$$S$$$ where we take $$${0s}$$$ and the remaining part where we take $$${1s}$$$.

Let $$$C_1$$$ be the total number of $$${1s}$$$. Then the length becomes:

But

So:

Thus, we need to maximize $$$(\text{0s} - \text{1s})$$$ over a cyclic segment.

Now map:

Then for any segment, its sum equals $$$(\text{0s} - \text{1s})$$$. So the problem reduces to finding the maximum subarray sum in a circular array.

Using Kadane's algorithm:

Final answer:

Time complexity is $$$O(n)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;

    int totalOnes = 0;
    int totalSum = 0;
    int maxSum = 0, curMax = 0;
    int minSum = 0, curMin = 0;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        if (x == 1) totalOnes++;

        int val = (x == 0 ? 1 : -1);
        totalSum += val;

        curMax = max(val, curMax + val);
        maxSum = max(maxSum, curMax);

        curMin = min(val, curMin + val);
        minSum = min(minSum, curMin);
    }

    int maxCircular = max(maxSum, totalSum - minSum);

    cout << totalOnes + maxCircular << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) solve();
}

The core equation is $$$(A[i] + A[j]) \times A[k] = X$$$. Notice that for any valid triple, $$$A[k]$$$ must be a divisor of $$$X$$$. Since $$$X \le 10^6$$$, the number of divisors is relatively small (at most 240).

For a fixed divisor $$$d$$$ of $$$X$$$, assume $$$A[k] = d$$$. The equation simplifies to $$$A[i] + A[j] = \frac{X}{d}$$$. Let $$$T = \frac{X}{d}$$$ be our target sum. We need to count triples $$$(i, k, j)$$$ such that $$$1 \le i \lt k \lt j \le n$$$, $$$A[k] = d$$$, and $$$A[i] + A[j] = T$$$.

To count these triples efficiently for a fixed $$$d$$$, iterate through the array from left to right. At each index $$$j$$$, if we treat $$$A[j]$$$ as the third element of the triple, we need to count how many pairs $$$(i, k)$$$ existed before it such that $$$i \lt k \lt j$$$ and $$$A[i] = T - A[j]$$$ while $$$A[k] = d$$$.

This can be managed by maintaining the cumulative count of $$$A[k]$$$ occurrences that appeared after each specific $$$A[i]$$$ value.

1. Find all divisors $$$d$$$ of $$$X$$$.

2. For each divisor $$$d$$$:

   • Let $$$T = X/d$$$.
   • Precompute a suffix array suf where suf[i] is the count of elements equal to $$$d$$$ in the range $$$[i, n-1]$$$.
   • Iterate through the array $$$A$$$ from $$$i = 0$$$ to $$$n-1$$$.
   • If $$$A[i]$$$ is treated as the third element $$$A[j]$$$, the number of valid $$$(i, k)$$$ pairs before it is: $$$\sum_{p \lt i, A[p] = T - A[i]} (\text{count of } d \text{ in range } (p, i))$$$
   • Using the suffix array, the count of $$$d$$$ in $$$(p, i)$$$ is $$$suf[p+1] - suf[i]$$$.
   • The total contribution for a fixed $$$i$$$ is: $$$\sum (suf[p+1] - suf[i]) = (\sum suf[p+1]) - (\text{count of } p \times suf[i])$$$
   • Maintain sum[v] as $$$\sum suf[p+1]$$$ and cnt[v] as the count of value $$$v$$$ seen so far.
3. Sum the results for all divisors.

Complexity: $$$O(\text{divisors}(X) \times n)$$$. With $$$n=10^6$$$ and a 6-second time limit, this approach is well within the limits.

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long ans = 0;
    vector<int> d;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d.push_back(i);
            if (i != (x / i)) d.push_back(x / i);
        }
    }

    int sz = (int) d.size();
    vector<long long> suf(n + 1, 0);
    vector<long long> sum(x + 1, 0), cnt(x + 1, 0);

    for (int k = 0; k < sz; k++) {
        int d_val = d[k];
        int tar = x / d_val;

        fill(suf.begin(), suf.end(), 0);
        fill(sum.begin(), sum.end(), 0);
        fill(cnt.begin(), cnt.end(), 0);

        for (int i = n - 1; i >= 0; i--) {
            suf[i] = suf[i + 1] + (a[i] == d_val);
        }

        long long cur = 0;
        for (int i = 0; i < n; i++) {
            int complement = tar - a[i];
            if (complement > 0 && complement < x) {
                cur += sum[complement] - cnt[complement] * suf[i];
            }

            if (a[i] < tar) {
                cnt[a[i]]++;
                sum[a[i]] += suf[i + 1];
            }
        }
        ans += cur;
    }
    cout << ans << endl;
}

int main() {
    fastio();
    solve();
    return 0;
}

Read the hints of Problem D

We are given two expressions

and we want to count when they are equal.

We start from the identity

Substituting:

which simplifies to

Now interpret this. Since we are working modulo $$$2^{m-1}$$$, the lowest $$$m-1$$$ bits of $$$(a \text{ AND } b)$$$ must be zero. In binary, the $$$i$$$-th bit of $$$(a \text{ AND } b)$$$ is $$$1$$$ only if both $$$a_i = 1$$$ and $$$b_i = 1$$$. Hence, for all $$$i \lt m-1$$$, both bits cannot be $$$1$$$ simultaneously. This means no carry should occur in the first $$$m-1$$$ bits.

Let $$$K = 2^{m-1}$$$. Then only the lowest $$$m-1$$$ bits matter, and the condition becomes

Now split every number as

where $$$r$$$ contains the lowest $$$m-1$$$ bits. The condition depends only on $$$r$$$, so we need

Now consider ranges $$$0 \le a \lt A$$$, $$$0 \le b \lt B$$$. Divide both into blocks of size $$$K$$$:

We reduce the problem to counting pairs $$$(r_a, r_b)$$$ such that

for some $$$X, Y \le K$$$. Let this count be $$$F(X,Y)$$$.

To compute $$$F(X,Y)$$$, we use prefix fixing. For $$$r_a \lt X$$$, pick a bit $$$i$$$ where $$$X$$$ has 1 and force $$$r_a$$$ to have 0 there while matching higher bits. Similarly pick $$$j$$$ for $$$r_b \lt Y$$$.

Fixing $$$(i,j)$$$, divide bits into three zones:

For $$$k \lt \min(i,j)$$$, both are free, so avoid $$$(1,1)$$$ giving $$$3$$$ choices per bit:

For bits between $$$i$$$ and $$$j$$$, one number is fixed. If the fixed bit is $$$1$$$, the other must be $$$0$$$; if it is $$$0$$$, the other has $$$2$$$ choices. This contributes:

For bits above both $$$i$$$ and $$$j$$$, both are fixed. If both have $$$1$$$ anywhere, the pair is invalid; otherwise valid.

Thus,

Summing over all valid $$$(i,j)$$$ gives $$$F(X,Y)$$$.

Finally, combine all block cases to get total valid pairs. The probability is

and the required answer is

The complexity is $$$O((\log M)^2)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MOD = 1e9 + 7;


int binexp(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1){
          ans *= a;
          ans %= MOD;
        }
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return ans;
}

/*
Counts pairs (x, y) such that:
0 <= x < A, 0 <= y < B and (x & y) = 0

Core idea:
- Fix prefix of A
- Choose divergence bits (i, j)
- Apply 3-zone counting logic
*/
int countValidPairs(int A, int B){
    int totalWays = 0;

    int fixedPrefixA = 0; // stores prefix while iterating bits

    for(int i = 31; i >= 0; i--){
        if((A >> i) & 1){

            // prefix sum of set bits in fixedPrefixA
            vector<int> prefixSetCount(32, 0);
            for(int j = 0; j <= 31; j++){
                prefixSetCount[j + 1] = prefixSetCount[j] + ((fixedPrefixA >> j) & 1);
            }

            int overlapPenalty = 0;

            for(int j = 31; j >= 0; j--){
                if((B >> j) & 1){

                    // number of "free choices" contributing to power of 2
                    int freePositions = abs(j - i) - max(0LL, prefixSetCount[j] - prefixSetCount[i + 1]);

                    int ways = binexp(2, freePositions - overlapPenalty) * binexp(3, min(i, j)) % MOD;

                    totalWays = (totalWays + ways) % MOD;

                    // update penalty for overlap
                    if(j < i) overlapPenalty++;

                    // if conflict in higher bits, stop
                    if((fixedPrefixA >> j) & 1) break;
                }
            }

            // include this bit in prefix
            fixedPrefixA |= (1LL << i);
        }
    }

    return totalWays;
}

void solve(){
    int A, B, M;
    cin >> A >> B >> M;

    // If M = 1 → everything mod 1 = 0 → always equal
    if(M == 1){
        cout << 1 << "\n";
        return;
    }

    int blockSize = M >> 1; // 2^(m-1)

    int totalA = A;
    int totalB = B;

    // Split into full blocks and remainder
    int A_fullBlocks = A / blockSize;
    int B_fullBlocks = B / blockSize;

    int A_partial = A % blockSize;
    int B_partial = B % blockSize;

    int validPairs = 0;

    // Case 1: full × full
    validPairs = (validPairs +
        (A_fullBlocks % MOD) * (B_fullBlocks % MOD) % MOD *
        countValidPairs(blockSize, blockSize) % MOD) % MOD;

    // Case 2: full × partial
    validPairs = (validPairs +
        (A_fullBlocks % MOD) * countValidPairs(blockSize, B_partial) % MOD) % MOD;

    // Case 3: partial × full
    validPairs = (validPairs +
        (B_fullBlocks % MOD) * countValidPairs(A_partial, blockSize) % MOD) % MOD;

    // Case 4: partial × partial
    validPairs = (validPairs + countValidPairs(A_partial, B_partial)) % MOD;

    int totalPairs = (totalA % MOD) * (totalB % MOD) % MOD;

    int answer = validPairs * binexp(totalPairs, MOD - 2) % MOD;

    cout << answer << "\n";
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) solve();

    return 0;
}

Key Idea

We start with the identity:

Substituting this into Nobita’s incorrect expression:

we get:

This simplifies to:

Since $$$M = 2^m$$$, dividing both sides by $$$2$$$ gives:

Binary Interpretation

A number is divisible by $$$2^{m-1}$$$ if and only if all its bits from index $$$0$$$ to $$$m-2$$$ are zero.

Thus, for every bit position:

we must ensure:

For bits:

there is no restriction from this condition, but we must still respect bounds imposed by $$$A$$$ and $$$B$$$.

Range Conversion

Given:

we convert to inclusive ranges:

We store binary representations:

Also compute:

Digit DP Definition

Define:

which counts the number of valid ways to construct bits of $$$a$$$ and $$$b$$$ from position $$$idx$$$ down to $$$0$$$.

• $$$idx$$$: current bit (starting from MSB, e.g., $$$30$$$)
• $$$tight_A$$$: whether prefix of $$$a$$$ equals $$$A$$$
• $$$tight_B$$$: whether prefix of $$$b$$$ equals $$$B$$$

If $$$tight_A = 1$$$, we must respect $$$A_i$$$, otherwise we can freely choose bits.
Same applies to $$$tight_B$$$.

Transition

At each state:

Choose:

We iterate over all pairs $$$(a_i, b_i)$$$.

Constraint

If:

then:

because this would set a bit in $$$(a & b)$$$

Updating Tight Flags

• If we match the boundary → remain tight
• Otherwise → become non-tight permanently

DP Transition

We memoize results to avoid recomputation.

Base Case

When:

all bits are assigned, so:

Final Answer

Total valid pairs:

Total possible pairs:

Required probability:

This is computed as:

where inverse is computed using fast exponentiation.

Complexity

• States: $$$O(30 \cdot 2 \cdot 2)$$$
• Transitions: constant

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MOD = 1e9 + 7;

int binexp(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1){
            ans = (ans * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ans;
}

int bitsA[35], bitsB[35];
int m_val;

// dp[idx][tightA][tightB]
int dp[35][2][2];

int solve_dp(int idx, int tightA, int tightB){
    if(idx < 0) return 1;

    if(dp[idx][tightA][tightB] != -1)
        return dp[idx][tightA][tightB];

    int ans = 0;

    int A_i = bitsA[idx];
    int B_i = bitsB[idx];

    int limitA = (tightA ? A_i : 1);
    int limitB = (tightB ? B_i : 1);

    for(int a_i = 0; a_i <= limitA; a_i++){
        for(int b_i = 0; b_i <= limitB; b_i++){

            // forbid (1,1) for idx < m-1
            if(idx < m_val - 1 && a_i == 1 && b_i == 1) continue;

            int nextTightA = tightA && (a_i == limitA);
            int nextTightB = tightB && (b_i == limitB);

            ans += solve_dp(idx - 1, nextTightA, nextTightB);
            ans %= MOD;
        }
    }

    return dp[idx][tightA][tightB] = ans;
}

void solve(){
    int A, B, M;
    cin >> A >> B >> M;

    int total = (A % MOD) * (B % MOD) % MOD;

    // convert to inclusive
    A--; 
    B--;

    // find m such that M = 2^m
    int m = 0;
    int temp = M;
    while(temp > 1){
        temp >>= 1;
        m++;
    }
    m_val = m;

    // store bits
    for(int i = 0; i <= 30; i++){
        bitsA[i] = (A >> i) & 1;
        bitsB[i] = (B >> i) & 1;
    }

    memset(dp, -1, sizeof(dp));

    int validCount = solve_dp(30, 1, 1);

    int ans = validCount * binexp(total, MOD - 2) % MOD;

    cout << ans << '\n';
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) solve();

    return 0;
}