Thank you for taking partparticipating in $\textmathbf{OPC\ March\ 2026}$. !↵
↵
This editorialwalks through the coreoutlines the key ideas and solution strategies behindapproaches for each problem. ↵
We hope it helps you learn something new and refinegain deeper insights and further strengthen your approach toblem-solving skills in competitive programming.↵
If you have any reviews please put them in↵
We would greatly appreciate your feedback. Please share your thoughts through this [Google Form](https://docs.google.com/forms/d/e/1FAIpQLSf2jvScUIwpxy16neU-CKQj7wIFx9diAO7vFY7TJSERR_PFwQ/viewform).↵
↵
↵
↵
↵
Contest Link: [Link](https://mirror.codeforces.com/group/hUywLYmr80/contest/66090478537)↵
↵
↵
↵
### [A. Find Sum](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/A)↵
↵
↵
<spoiler summary="Hint 1">↵
To make a sum of differences as large as possible, you want to subtract the smallest available numbers and add the largest available numbers.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The cost function is $Cost = |a_n - a_1| + \sum_{i=2}^{n} |a_i - a_{i-1}|$. This is equivalent to the total distance traveled if you start at $a_1$, visit all points in the permutation order, and then return from $a_n$ to $a_1$.↵
↵
In any absolute difference $|x - y|$, one number is treated as positive and the other as negative. Across the entire sum, there are $2n$ terms (since each of the $n$ elements appears in two difference pairs). To maximize the sum, we want:↵
↵
The largest numbers to have a positive sign as often as possible.↵
↵
The smallest numbers to have a negative sign as often as possible.↵
↵
For any $n$, we can pick the $\lfloor n/2 \rfloor$ smallest integers and the $\lfloor n/2 \rfloor$ largest integers.↵
↵
The small integers $[1, 2, \dots, \lfloor n/2 \rfloor]$ will each contribute twice with a negative sign.↵
↵
The large integers $[(n - \lfloor n/2 \rfloor + 1), \dots, n]$ will each contribute twice with a positive sign.↵
↵
If $n$ is odd, the middle element contributes once as a positive and once as a negative (effectively canceling itself out).↵
↵
This leads us to the maximum sum formula:$$Cost = 2 \cdot \left( \sum \text{Largest } \lfloor n/2 \rfloor \text{ elements} - \sum \text{Smallest } \lfloor n/2 \rfloor \text{ elements} \right)$$↵
</spoiler>↵
↵
↵
<spoiler summary="Code (C++)">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
if (!(cin >> t)) return 0;↵
while (t--) {↵
long long n;↵
cin >> n;↵
cout << (n * n / 2) << '\n';↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
Author: [user:mnnit.prakharg,2026-03-17]↵
↵
---↵
↵
### [B: Count Equal](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/B)↵
↵
<spoiler summary="Hint 1">↵
Iterate on the leftmost set bit, and count how many valid integers have that bit as their leftmost set bit.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
Author: [user:mnnit.prakharg,2026-03-17]↵
↵
---↵
↵
### [C: Easy or Hard?](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/C)↵
↵
<spoiler summary="Hint 1">↵
Try fixing the first two elements and generate the sequence using the rule↵
$a_i \oplus a_{i+1} = a_{i+2}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We are given that:↵
$$↵
a_i \oplus a_{i+1} = a_{i+2}↵
$$↵
↵
Fix the first two elements $a_1 = x$ and $a_2 = y$.↵
↵
Then:↵
$$↵
a_3 = x \oplus y↵
$$↵
$$↵
a_4 = y \oplus (x \oplus y) = x↵
$$↵
$$↵
a_5 = (x \oplus y) \oplus x = y↵
$$↵
↵
So the sequence becomes:↵
$$↵
x,\ y,\ x \oplus y,\ x,\ y,\ x \oplus y,\dots↵
$$↵
↵
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:↵
$$↵
\max(f_1, f_2, f_3) - \min(f_1, f_2, f_3) \le 1↵
$$↵
↵
If this condition holds, we can arrange elements in cyclic order and the answer is $\textbf{YES}$, otherwise $\textbf{NO}$.↵
↵
$\textbf{Complexity}$: $O(n)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
unordered_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");↵
}↵
}↵
```↵
</spoiler>↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
### [D. Nobita and the Divine Probability (Easy Version)](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/D)↵
↵
<spoiler summary="Hint 1">↵
Use the identity $a + b = (a \oplus b) + 2(a \text{ AND } b)$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Think about when addition and XOR differ — it happens due to carries.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Since modulo is $2^m$, only the lowest $m$ bits matter. Try avoiding carries in the first $m-1$ bits.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
We are given two expressions↵
$$↵
(a \oplus b) \bmod 2^m \quad \text{and} \quad (a + b) \bmod 2^m↵
$$↵
and need to find when they are equal.↵
↵
We start with the identity↵
$$↵
a + b = (a \oplus b) + 2(a \text{ AND } b)↵
$$↵
Substituting, the condition becomes↵
$$↵
(a \oplus b) \equiv (a \oplus b) + 2(a \text{ AND } b) \pmod{2^m}↵
$$↵
which simplifies to↵
$$↵
2(a \text{ AND } b) \equiv 0 \pmod{2^m}↵
$$↵
or↵
$$↵
(a \text{ AND } b) \equiv 0 \pmod{2^{m-1}}↵
$$↵
↵
↵
$\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 < 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↵
$$↵
(a \bmod 2^{m-1}) \text{ AND } (b \bmod 2^{m-1}) = 0↵
$$↵
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↵
$$↵
C = \max(0, \min(x, y, m-1))↵
$$↵
↵
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↵
$$↵
\left(\frac{3}{4}\right)^C↵
$$↵
↵
Thus the required probability is↵
$$↵
\frac{3^C}{4^C}↵
$$↵
and we compute↵
$$↵
3^C \cdot (4^C)^{-1} \bmod (10^9+7)↵
$$↵
↵
The solution runs in $O(\log MOD)$ per test case using fast exponentiation.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
### [E. Cyclic Non-Decreasing Subsequence](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/E)↵
↵
<spoiler summary="Hint 1">↵
In a binary array, what does a non-decreasing subsequence look like? Try to describe its structure.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Try maximizing $(\text{number of 0s} - \text{number of 1s})$ over a cyclic segment. Can you reduce this to a known problem?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
A non-decreasing subsequence in a binary array must be of the form↵
$$↵
0,0,\dots,0,1,1,\dots,1↵
$$↵
↵
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:↵
$$↵
\text{Length} = (\text{0s in } S) + (\text{1s outside } S)↵
$$↵
But↵
$$↵
\text{1s outside } S = C_1 - (\text{1s in } S)↵
$$↵
So:↵
$$↵
\text{Length} = C_1 + (\text{0s in } S - \text{1s in } S)↵
$$↵
↵
Thus, we need to maximize $(\text{0s} - \text{1s})$ over a cyclic segment.↵
↵
Now map:↵
$$↵
0 \rightarrow +1,\quad 1 \rightarrow -1↵
$$↵
↵
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:↵
$$↵
\text{maxCircular} = \max(\text{maxSum},\ \text{totalSum} - \text{minSum})↵
$$↵
↵
Final answer:↵
$$↵
\text{answer} = C_1 + \text{maxCircular}↵
$$↵
↵
Time complexity is $O(n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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();↵
}↵
```↵
</spoiler>↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
### [F. Fun Is Counting](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/F)↵
↵
<spoiler summary="Hint 1">↵
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).↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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 < k < j \le n$, $A[k] = d$, and $A[i] + A[j] = T$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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 < k < 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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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 < 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)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
↵
#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;↵
}↵
↵
```↵
</spoiler>↵
↵
Author: [user:late_night_dreams,2026-03-17]↵
↵
---↵
↵
### [G. Nobita and the Divine Probability (Hard Version)](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/G)↵
↵
<spoiler summary="Legendary Hint">↵
Read the hints of Problem D↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
We are given two expressions↵
$$↵
(a \oplus b) \bmod 2^m \quad \text{and} \quad (a + b) \bmod 2^m↵
$$↵
and we want to count when they are equal.↵
↵
We start from the identity↵
$$↵
a + b = (a \oplus b) + 2(a \text{ AND } b)↵
$$↵
Substituting:↵
$$↵
(a \oplus b) \equiv (a \oplus b) + 2(a \text{ AND } b) \pmod{2^m}↵
$$↵
which simplifies to↵
$$↵
2(a \text{ AND } b) \equiv 0 \pmod{2^m}↵
\Rightarrow (a \text{ AND } b) \equiv 0 \pmod{2^{m-1}}↵
$$↵
↵
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 < 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↵
$$↵
(a \text{ AND } b \text{ AND } (K - 1)) = 0↵
$$↵
↵
Now split every number as↵
$$↵
x = q \cdot K + r↵
$$↵
where $r$ contains the lowest $m-1$ bits. The condition depends only on $r$, so we need↵
$$↵
r_a \text{ AND } r_b = 0↵
$$↵
↵
Now consider ranges $0 \le a < A$, $0 \le b < B$. Divide both into blocks of size $K$:↵
$$↵
A = A_{\text{blocks}} \cdot K + A_{\text{rem}}, \quad↵
B = B_{\text{blocks}} \cdot K + B_{\text{rem}}↵
$$↵
↵
We reduce the problem to counting pairs $(r_a, r_b)$ such that↵
$$↵
r_a < X,\quad r_b < Y,\quad r_a \text{ AND } r_b = 0↵
$$↵
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 < 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 < Y$.↵
↵
Fixing $(i,j)$, divide bits into three zones:↵
↵
For $k < \min(i,j)$, both are free, so avoid $(1,1)$ giving $3$ choices per bit:↵
$$↵
3^{\min(i,j)}↵
$$↵
↵
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:↵
$$↵
2^{(\text{number of zero bits in prefix})}↵
$$↵
↵
For bits above both $i$ and $j$, both are fixed. If both have $1$ anywhere, the pair is invalid; otherwise valid.↵
↵
Thus,↵
$$↵
\text{Ways}(i,j) = (\text{validity}) \times 2^{(\text{zeros})} \times 3^{\min(i,j)}↵
$$↵
↵
Summing over all valid $(i,j)$ gives $F(X,Y)$.↵
↵
Finally, combine all block cases to get total valid pairs. The probability is↵
$$↵
\frac{\text{valid pairs}}{A \cdot B}↵
$$↵
and the required answer is↵
$$↵
\text{valid pairs} \cdot (A \cdot B)^{-1} \bmod (10^9+7)↵
$$↵
↵
The complexity is $O((\log M)^2)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
## Key Idea↵
↵
We start with the identity:↵
$$↵
a + b = (a \oplus b) + 2(a \& b).↵
$$↵
↵
Substituting this into Nobita’s incorrect expression:↵
$$↵
(a + b) \equiv (a \oplus b) \pmod{M},↵
$$↵
we get:↵
$$↵
(a \oplus b + 2(a \& b)) \equiv (a \oplus b) \pmod{M}.↵
$$↵
↵
This simplifies to:↵
$$↵
2(a \& b) \equiv 0 \pmod{M}.↵
$$↵
↵
Since $M = 2^m$, dividing both sides by $2$ gives:↵
$$↵
(a \& b) \equiv 0 \pmod{2^{m-1}}.↵
$$↵
↵
---↵
↵
## 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:↵
$$↵
i < m-1,↵
$$↵
we must ensure:↵
$$↵
(a_i, b_i) \neq (1,1).↵
$$↵
↵
For bits:↵
$$↵
i \ge m-1,↵
$$↵
there is no restriction from this condition, but we must still respect bounds imposed by $A$ and $B$.↵
↵
---↵
↵
## Range Conversion↵
↵
Given:↵
$$↵
0 \le a < A, \quad 0 \le b < B,↵
$$↵
↵
we convert to inclusive ranges:↵
$$↵
A := A - 1, \quad B := B - 1.↵
$$↵
↵
We store binary representations:↵
$$↵
A_i = \text{bitsA}[i], \quad B_i = \text{bitsB}[i].↵
$$↵
↵
Also compute:↵
$$↵
M = 2^m.↵
$$↵
↵
---↵
↵
## Digit DP Definition↵
↵
Define:↵
$$↵
dp(idx, tight_A, tight_B),↵
$$↵
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:↵
$$↵
limit_A = (tight_A ? A_i : 1), \quad↵
limit_B = (tight_B ? B_i : 1).↵
$$↵
↵
Choose:↵
$$↵
a_i \in [0, limit_A], \quad b_i \in [0, limit_B].↵
$$↵
↵
We iterate over all pairs $(a_i, b_i)$.↵
↵
### Constraint↵
↵
If:↵
$$↵
idx < m-1,↵
$$↵
then:↵
$$↵
(a_i, b_i) \neq (1,1),↵
$$↵
↵
↵
because this would set a bit in $(a \&text{&} b)$↵
↵
↵
---↵
↵
## Updating Tight Flags↵
↵
$$↵
nextTight_A = tight_A \land (a_i = limit_A),↵
$$↵
$$↵
nextTight_B = tight_B \land (b_i = limit_B).↵
$$↵
↵
- If we match the boundary → remain tight ↵
- Otherwise → become non-tight permanently↵
↵
---↵
↵
## DP Transition↵
↵
$$↵
dp(idx, tight_A, tight_B) += dp(idx - 1, nextTight_A, nextTight_B).↵
$$↵
↵
We memoize results to avoid recomputation.↵
↵
---↵
↵
## Base Case↵
↵
When:↵
$$↵
idx < 0,↵
$$↵
all bits are assigned, so:↵
$$↵
dp(idx, \cdot, \cdot) = 1.↵
$$↵
↵
---↵
↵
## Final Answer↵
↵
Total valid pairs:↵
$$↵
\text{validCount} = dp(30, 1, 1).↵
$$↵
↵
Total possible pairs:↵
$$↵
A \cdot B.↵
$$↵
↵
Required probability:↵
$$↵
\frac{\text{validCount}}{A \cdot B} \bmod (10^9 + 7).↵
$$↵
↵
This is computed as:↵
$$↵
\text{validCount} \cdot (A \cdot B)^{-1} \bmod (10^9 + 7),↵
$$↵
↵
where inverse is computed using fast exponentiation.↵
↵
---↵
↵
## Complexity↵
↵
- States: $O(30 \cdot 2 \cdot 2)$ ↵
- Transitions: constant ↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
↵
↵
↵
This editorial
We would greatly appreciate your feedback. Please share your thoughts through this [Google Form](https://docs.google.com/forms/d/e/1FAIpQLSf2jvScUIwpxy16neU-CKQj7wIFx9diAO7vFY7TJSERR_PFwQ/viewform)
↵
↵
↵
↵
Contest Link: [Link](https://mirror.codeforces.com/group/hUywLYmr80/contest/6
↵
↵
↵
### [A. Find Sum](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/A)↵
↵
↵
<spoiler summary="Hint 1">↵
To make a sum of differences as large as possible, you want to subtract the smallest available numbers and add the largest available numbers.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The cost function is $Cost = |a_n - a_1| + \sum_{i=2}^{n} |a_i - a_{i-1}|$. This is equivalent to the total distance traveled if you start at $a_1$, visit all points in the permutation order, and then return from $a_n$ to $a_1$.↵
↵
In any absolute difference $|x - y|$, one number is treated as positive and the other as negative. Across the entire sum, there are $2n$ terms (since each of the $n$ elements appears in two difference pairs). To maximize the sum, we want:↵
↵
The largest numbers to have a positive sign as often as possible.↵
↵
The smallest numbers to have a negative sign as often as possible.↵
↵
For any $n$, we can pick the $\lfloor n/2 \rfloor$ smallest integers and the $\lfloor n/2 \rfloor$ largest integers.↵
↵
The small integers $[1, 2, \dots, \lfloor n/2 \rfloor]$ will each contribute twice with a negative sign.↵
↵
The large integers $[(n - \lfloor n/2 \rfloor + 1), \dots, n]$ will each contribute twice with a positive sign.↵
↵
If $n$ is odd, the middle element contributes once as a positive and once as a negative (effectively canceling itself out).↵
↵
This leads us to the maximum sum formula:$$Cost = 2 \cdot \left( \sum \text{Largest } \lfloor n/2 \rfloor \text{ elements} - \sum \text{Smallest } \lfloor n/2 \rfloor \text{ elements} \right)$$↵
</spoiler>↵
↵
↵
<spoiler summary="Code (C++)">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
if (!(cin >> t)) return 0;↵
while (t--) {↵
long long n;↵
cin >> n;↵
cout << (n * n / 2) << '\n';↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
Author: [user:mnnit.prakharg,2026-03-17]↵
↵
---↵
↵
### [B: Count Equal](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/B)↵
↵
<spoiler summary="Hint 1">↵
Iterate on the leftmost set bit, and count how many valid integers have that bit as their leftmost set bit.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
Author: [user:mnnit.prakharg,2026-03-17]↵
↵
---↵
↵
### [C: Easy or Hard?](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/C)↵
↵
<spoiler summary="Hint 1">↵
Try fixing the first two elements and generate the sequence using the rule↵
$a_i \oplus a_{i+1} = a_{i+2}$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We are given that:↵
$$↵
a_i \oplus a_{i+1} = a_{i+2}↵
$$↵
↵
Fix the first two elements $a_1 = x$ and $a_2 = y$.↵
↵
Then:↵
$$↵
a_3 = x \oplus y↵
$$↵
$$↵
a_4 = y \oplus (x \oplus y) = x↵
$$↵
$$↵
a_5 = (x \oplus y) \oplus x = y↵
$$↵
↵
So the sequence becomes:↵
$$↵
x,\ y,\ x \oplus y,\ x,\ y,\ x \oplus y,\dots↵
$$↵
↵
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:↵
$$↵
\max(f_1, f_2, f_3) - \min(f_1, f_2, f_3) \le 1↵
$$↵
↵
If this condition holds, we can arrange elements in cyclic order and the answer is $\textbf{YES}$, otherwise $\textbf{NO}$.↵
↵
$\textbf{Complexity}$: $O(n)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
unordered_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");↵
}↵
}↵
```↵
</spoiler>↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
### [D. Nobita and the Divine Probability (Easy Version)](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/D)↵
↵
<spoiler summary="Hint 1">↵
Use the identity $a + b = (a \oplus b) + 2(a \text{ AND } b)$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Think about when addition and XOR differ — it happens due to carries.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Since modulo is $2^m$, only the lowest $m$ bits matter. Try avoiding carries in the first $m-1$ bits.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
We are given two expressions↵
$$↵
(a \oplus b) \bmod 2^m \quad \text{and} \quad (a + b) \bmod 2^m↵
$$↵
and need to find when they are equal.↵
↵
We start with the identity↵
$$↵
a + b = (a \oplus b) + 2(a \text{ AND } b)↵
$$↵
Substituting, the condition becomes↵
$$↵
(a \oplus b) \equiv (a \oplus b) + 2(a \text{ AND } b) \pmod{2^m}↵
$$↵
which simplifies to↵
$$↵
2(a \text{ AND } b) \equiv 0 \pmod{2^m}↵
$$↵
or↵
$$↵
(a \text{ AND } b) \equiv 0 \pmod{2^{m-1}}↵
$$↵
↵
↵
$\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 < 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↵
$$↵
(a \bmod 2^{m-1}) \text{ AND } (b \bmod 2^{m-1}) = 0↵
$$↵
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↵
$$↵
C = \max(0, \min(x, y, m-1))↵
$$↵
↵
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↵
$$↵
\left(\frac{3}{4}\right)^C↵
$$↵
↵
Thus the required probability is↵
$$↵
\frac{3^C}{4^C}↵
$$↵
and we compute↵
$$↵
3^C \cdot (4^C)^{-1} \bmod (10^9+7)↵
$$↵
↵
The solution runs in $O(\log MOD)$ per test case using fast exponentiation.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
### [E. Cyclic Non-Decreasing Subsequence](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/E)↵
↵
<spoiler summary="Hint 1">↵
In a binary array, what does a non-decreasing subsequence look like? Try to describe its structure.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Try maximizing $(\text{number of 0s} - \text{number of 1s})$ over a cyclic segment. Can you reduce this to a known problem?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
A non-decreasing subsequence in a binary array must be of the form↵
$$↵
0,0,\dots,0,1,1,\dots,1↵
$$↵
↵
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:↵
$$↵
\text{Length} = (\text{0s in } S) + (\text{1s outside } S)↵
$$↵
But↵
$$↵
\text{1s outside } S = C_1 - (\text{1s in } S)↵
$$↵
So:↵
$$↵
\text{Length} = C_1 + (\text{0s in } S - \text{1s in } S)↵
$$↵
↵
Thus, we need to maximize $(\text{0s} - \text{1s})$ over a cyclic segment.↵
↵
Now map:↵
$$↵
0 \rightarrow +1,\quad 1 \rightarrow -1↵
$$↵
↵
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:↵
$$↵
\text{maxCircular} = \max(\text{maxSum},\ \text{totalSum} - \text{minSum})↵
$$↵
↵
Final answer:↵
$$↵
\text{answer} = C_1 + \text{maxCircular}↵
$$↵
↵
Time complexity is $O(n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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();↵
}↵
```↵
</spoiler>↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
### [F. Fun Is Counting](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/F)↵
↵
<spoiler summary="Hint 1">↵
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).↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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 < k < j \le n$, $A[k] = d$, and $A[i] + A[j] = T$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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 < k < 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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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 < 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)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
↵
#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;↵
}↵
↵
```↵
</spoiler>↵
↵
Author: [user:late_night_dreams,2026-03-17]↵
↵
---↵
↵
### [G. Nobita and the Divine Probability (Hard Version)](https://mirror.codeforces.com/group/hUywLYmr80/contest/678537/problem/G)↵
↵
<spoiler summary="Legendary Hint">↵
Read the hints of Problem D↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
We are given two expressions↵
$$↵
(a \oplus b) \bmod 2^m \quad \text{and} \quad (a + b) \bmod 2^m↵
$$↵
and we want to count when they are equal.↵
↵
We start from the identity↵
$$↵
a + b = (a \oplus b) + 2(a \text{ AND } b)↵
$$↵
Substituting:↵
$$↵
(a \oplus b) \equiv (a \oplus b) + 2(a \text{ AND } b) \pmod{2^m}↵
$$↵
which simplifies to↵
$$↵
2(a \text{ AND } b) \equiv 0 \pmod{2^m}↵
\Rightarrow (a \text{ AND } b) \equiv 0 \pmod{2^{m-1}}↵
$$↵
↵
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 < 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↵
$$↵
(a \text{ AND } b \text{ AND } (K - 1)) = 0↵
$$↵
↵
Now split every number as↵
$$↵
x = q \cdot K + r↵
$$↵
where $r$ contains the lowest $m-1$ bits. The condition depends only on $r$, so we need↵
$$↵
r_a \text{ AND } r_b = 0↵
$$↵
↵
Now consider ranges $0 \le a < A$, $0 \le b < B$. Divide both into blocks of size $K$:↵
$$↵
A = A_{\text{blocks}} \cdot K + A_{\text{rem}}, \quad↵
B = B_{\text{blocks}} \cdot K + B_{\text{rem}}↵
$$↵
↵
We reduce the problem to counting pairs $(r_a, r_b)$ such that↵
$$↵
r_a < X,\quad r_b < Y,\quad r_a \text{ AND } r_b = 0↵
$$↵
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 < 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 < Y$.↵
↵
Fixing $(i,j)$, divide bits into three zones:↵
↵
For $k < \min(i,j)$, both are free, so avoid $(1,1)$ giving $3$ choices per bit:↵
$$↵
3^{\min(i,j)}↵
$$↵
↵
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:↵
$$↵
2^{(\text{number of zero bits in prefix})}↵
$$↵
↵
For bits above both $i$ and $j$, both are fixed. If both have $1$ anywhere, the pair is invalid; otherwise valid.↵
↵
Thus,↵
$$↵
\text{Ways}(i,j) = (\text{validity}) \times 2^{(\text{zeros})} \times 3^{\min(i,j)}↵
$$↵
↵
Summing over all valid $(i,j)$ gives $F(X,Y)$.↵
↵
Finally, combine all block cases to get total valid pairs. The probability is↵
$$↵
\frac{\text{valid pairs}}{A \cdot B}↵
$$↵
and the required answer is↵
$$↵
\text{valid pairs} \cdot (A \cdot B)^{-1} \bmod (10^9+7)↵
$$↵
↵
The complexity is $O((\log M)^2)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
## Key Idea↵
↵
We start with the identity:↵
$$↵
a + b = (a \oplus b) + 2(a \& b).↵
$$↵
↵
Substituting this into Nobita’s incorrect expression:↵
$$↵
(a + b) \equiv (a \oplus b) \pmod{M},↵
$$↵
we get:↵
$$↵
(a \oplus b + 2(a \& b)) \equiv (a \oplus b) \pmod{M}.↵
$$↵
↵
This simplifies to:↵
$$↵
2(a \& b) \equiv 0 \pmod{M}.↵
$$↵
↵
Since $M = 2^m$, dividing both sides by $2$ gives:↵
$$↵
(a \& b) \equiv 0 \pmod{2^{m-1}}.↵
$$↵
↵
---↵
↵
## 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:↵
$$↵
i < m-1,↵
$$↵
we must ensure:↵
$$↵
(a_i, b_i) \neq (1,1).↵
$$↵
↵
For bits:↵
$$↵
i \ge m-1,↵
$$↵
there is no restriction from this condition, but we must still respect bounds imposed by $A$ and $B$.↵
↵
---↵
↵
## Range Conversion↵
↵
Given:↵
$$↵
0 \le a < A, \quad 0 \le b < B,↵
$$↵
↵
we convert to inclusive ranges:↵
$$↵
A := A - 1, \quad B := B - 1.↵
$$↵
↵
We store binary representations:↵
$$↵
A_i = \text{bitsA}[i], \quad B_i = \text{bitsB}[i].↵
$$↵
↵
Also compute:↵
$$↵
M = 2^m.↵
$$↵
↵
---↵
↵
## Digit DP Definition↵
↵
Define:↵
$$↵
dp(idx, tight_A, tight_B),↵
$$↵
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:↵
$$↵
limit_A = (tight_A ? A_i : 1), \quad↵
limit_B = (tight_B ? B_i : 1).↵
$$↵
↵
Choose:↵
$$↵
a_i \in [0, limit_A], \quad b_i \in [0, limit_B].↵
$$↵
↵
We iterate over all pairs $(a_i, b_i)$.↵
↵
### Constraint↵
↵
If:↵
$$↵
idx < m-1,↵
$$↵
then:↵
$$↵
(a_i, b_i) \neq (1,1),↵
$$↵
↵
↵
because this would set a bit in $
↵
↵
---↵
↵
## Updating Tight Flags↵
↵
$$↵
nextTight_A = tight_A \land (a_i = limit_A),↵
$$↵
$$↵
nextTight_B = tight_B \land (b_i = limit_B).↵
$$↵
↵
- If we match the boundary → remain tight ↵
- Otherwise → become non-tight permanently↵
↵
---↵
↵
## DP Transition↵
↵
$$↵
dp(idx, tight_A, tight_B) += dp(idx - 1, nextTight_A, nextTight_B).↵
$$↵
↵
We memoize results to avoid recomputation.↵
↵
---↵
↵
## Base Case↵
↵
When:↵
$$↵
idx < 0,↵
$$↵
all bits are assigned, so:↵
$$↵
dp(idx, \cdot, \cdot) = 1.↵
$$↵
↵
---↵
↵
## Final Answer↵
↵
Total valid pairs:↵
$$↵
\text{validCount} = dp(30, 1, 1).↵
$$↵
↵
Total possible pairs:↵
$$↵
A \cdot B.↵
$$↵
↵
Required probability:↵
$$↵
\frac{\text{validCount}}{A \cdot B} \bmod (10^9 + 7).↵
$$↵
↵
This is computed as:↵
$$↵
\text{validCount} \cdot (A \cdot B)^{-1} \bmod (10^9 + 7),↵
$$↵
↵
where inverse is computed using fast exponentiation.↵
↵
---↵
↵
## Complexity↵
↵
- States: $O(30 \cdot 2 \cdot 2)$ ↵
- Transitions: constant ↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code (C++)">↵
```↵
#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;↵
}↵
```↵
</spoiler>↵
↵
↵
Author: [user:NPsolved.cpp,2026-03-17]↵
↵
---↵
↵
↵
↵
