---
tags: VNOJ, THT, Medium Implementation, Implementation, DP, DP-digit, Bit Manipulation, Math, Duy_e
---

Tin học trẻ 2021 - Vòng sơ khảo - Bảng C - Tổng XOR
===

[https://oj.vnoi.info/problem/tht21_skc_xor](https://oj.vnoi.info/problem/tht21_skc_xor)

-----
###### Tags: `DP-digit`, `Bit Manipulation`, `Brute Forces`, `Math`
###### Contributor: @[SPyofgame](https://codeforces.com/profile/SPyofgame)

[TOC]

-----
### Hướng dẫn subtask 1

Ở subtask này, dễ thấy ta chỉ cần duyệt qua từng $X$ trong đoạn từ $L$ đến $R$ và tính kết quả với từng $X$. Sau đó ta duy trì một biến ```ans``` để lưu kết quả tốt nhất hiện tại.

Về phần đếm, ta duy trì một biến ```cnt``` để đếm số lượng hiện tại của ```ans```. Lúc này ta có hai trường hợp cần cập nhật:

***Trường hợp 1:*** Nếu kết quả của $X$ hiện tại ta đang xét lớn hơn ```ans```, ta cập nhật ```ans``` thành kết quả này và gán ```cnt = 1```.
***Trường hợp 2:*** Nếu kết quả của $X$ hiện tại ta đang xét bằng với ```ans```, ta tăng ```cnt``` lên một.

-----
### Code cho subtask 1
> Duyệt qua từng $X$: $O(R-L)$
> Với mỗi $X$ tính tổng các $b_{i}$: $O(N)$
> Tổng độ phức tạp là $O((R-L)*N)$
> **Time:** $O((R-L)*N)$
> **Space:** $O(N)$
> **Algo:** Brute force
> [color=lightgreen]

:::success
:::spoiler Code

#include <iostream>
using namespace std;

const long long N = 200;

int a[N], n, L, R, K;

int cal(int X){ // calculate the sum for X
    int ans = 0;
    for (int i = 1; i <= n; i ++)
        ans += a[i]^X;
    return ans;
}

int main(){
// Fast IO
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> L >> R >> K;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    int ans = 0, cnt = 0;

    for (int X = L; X <= R; X ++)
        if (X % K == 0) {
            int ans_for_cur_X = cal(X);

            if (ans_for_cur_X == ans)
                cnt ++;
            else if (ans_for_cur_X > ans)
                ans = ans_for_cur_X, cnt = 1; 

        }

    cout << ans << '\n' << cnt;

    return 0;
}

:::

-----
### Hướng dẫn subtask 2

***Note***: ở đây dấu $\oplus$ có nghĩa là phép xor.

***Gợi ý 1:*** $L = 0, R = 2^{29} - 1, K = 1, 0 \leq a_{i} \le 2^{29} - 1$
***Gợi ý 2:*** Mọi cặp số nguyên không âm thuộc đoạn $[L..R]$ khi $xor$ lại sẽ cho kết quả không vượt quá $R$.
***Gợi ý 3:*** Các số cần xét đều thuộc dạng số nguyên có 29 bit !!

Đầu tiên, như hai gợi ý đầu, mọi $X$ thuộc $[L..R]$ đều hợp lệ (đều chia hết cho $K=1$). Và mọi giá trị $a_{i}$ đều thuộc $[L..R]$.

***Note:*** Vì đây là mấu chốt để giải cả những subtask sau nên mình sẽ nói rất kĩ.

Ở đây, ta cần biết về ý nghĩ của biểu diễn bit một số.
***Cụ thể ở đây là biểu diễn số thập phân sang nhị phân, nhưng ghi ngược chiều. (từ $4_{10} = 100_{2}$, ta biểu diễn thành $4_{10} = 001_{2}$ )***

Xét số nguyên $A = 4$ có biểu diễn bit là ```001```. Khi đánh số bit từ trái sang phải với chỉ số bắt đầu từ 0. Thì ta có thể tính được số $A$ theo cách sau:
> Xét từng chỉ số của biểu diễn nhị phân của $A$, ta sẽ đưa {bit hiện tại} nhân cho 2 lũy thừa {chỉ số} vào tổng.

#### Code giải thích cho cách chuyển

#include <string>
#include <iostream>
using namespace std;

long long Get_Dec(string Binary_presentation){
// Khi truyền A = 001 vào thì hàm sẽ trả về 4

    int size = Binary_presentation.size();
    int A = 0;
    for (int i = 0; i < size; i ++){
        int u;
        if (Binary_presentation[i] == '1') u = 1; else u = 0;

        A += u*(1 << i); // 1 << x = 2^x
    }
    
    return A;
}

int main(){
    cout << Get_Dec("001") << '\n'; // output: 4
    cout << Get_Dec("011") << '\n'; // output: 6
}

Vì $\forall a_{i}, 0 \le a_{i} \le 2^{29} - 1$, nên ta sẽ biểu diễn mỗi số trong dãy $a$ theo 29 bit nhị phân được đánh số từ $0$ đến $28$.

Khi biết được tính chất của bit và đã biểu diễn lại dãy $a$, ta có thể biểu diễn lại tổng dãy $a$ của đề như sau:

* Đầu tiên biểu diễn lại dãy $a$ theo ma trận nhị phân:

a = {1, 4, 6, 5}

a[0] : 1000
a[1] : 0010
a[2] : 0110
a[3] : 1010

* Đánh số cột từ 0, ta có $cnt[i]$ là tổng của cột $i$, hay có thể hiểu là số lượng bit $1$ có ở cột $i$
* Rõ ràng để tính tổng của cả mảng $a$ ta chỉ cần tính tổng của các $cnt[i] \times 2^{i}$

Phần còn lại là xử lý phép xor.

Một lần nữa biểu diễn dãy $a$ thành ma trận, lần này ta sẽ thêm cả $X$:

a = {1, 4, 6, 5}
X = 5: 1010

a[0] : 1000       |a[0] ⊕ X : 0010 
a[1] : 0010  ->   |a[1] ⊕ X : 1000
a[2] : 0110       |a[2] ⊕ X : 1100
a[3] : 1010       |a[3] ⊕ X : 0000

Ta có, $1 \oplus 1 = 0$ và $0 \oplus 1 = 1$

Lúc này, ta tính tổng của từng ${a_{i}}\oplus
{X}$, dựa vào ma trận trên có thể thấy khi ta biểu diễn từng $a_{i}\oplus
X$, nếu ở cột $i$ và bit của $i$ của $X$ là `1` thì mọi bit của cột $i$ sẽ lật đồng thời $cnt[i]$ lúc này cũng thay đổi, cụ thể $cnt[i]$ đổi thành $n - cnt[i]$

$L = 0, R = 2^{29} - 1, K = 1, a_{i} \le 2^{29} - 1$ nên thay vì tìm $X$ ta sẽ điều chỉnh từng bit trong $X$ sao cho ta có thể đạt được giá trị lớn nhất.

Về phần đếm xin trình bày trong code. Lúc này ta có thể giải như sau.

-----
### Code cho subtask 2
> Ở mỗi $i$ ta check từng bit của $a[i]$: $O(29)$ mỗi $i$
> Nên phần precalculate: $O(29 \times N)$
> Phần tính kết quả: $O(29)$
> Độ phức tạp tổng $O(29 \times N) + O(29) = O(29 \times N)$
>**Time:** $O(29 \times N)$
>**Space:** $O(N)$
>**Algo:** Bit Manipulation, Math

> [color=lightgreen]
:::success
:::spoiler Code
#include <iostream>
using namespace std;
const long long N = 1e5 + 5;
const long long lg = 29; // số lượng bit
int a[N], n, L, R, K;

int cnt[lg]; // tổng của cột trong bảng

int main(){
cin >> n >> L >> R >> K;

for (int i = 1; i <= n; i ++){
cin >> a[i];

for (int j = 0; j < lg; j ++){ // lúc này ta làm việc với bảng có đủ 29 cột và n hàng

if (a[i] & (1 << j)) // xét xem bit thứ j của a[i] là bit 1 hay 0.
cnt[j] ++; // bạn có thể viết hàm chuyển số sang string

}
}

long long ans = 0, number_of_X = 1;
// Luôn có thể tìm được X

// xét từ bit có bậc cao nhất về bit có bậc thấp nhất. (most significant bit)

for (int i = lg - 1; i >= 0; i --){

// xét 2 case:

// case 1: bit i là 0, không làm lật cột i

long long Case_1 = cnt[i]*(1ll << i); // 1 << i = 2 mũ i

// case 2: bit i là 1, làm lật toàn bộ cột i

long long Case_2 = (n - cnt[i])*(1ll << i);

if (Case_2 > Case_1)
ans += Case_2;

if (Case_1 > Case_2)
ans += Case_1;

if (Case_1 == Case_2)
ans += Case_1, number_of_X *= 2;
/*

Xét số X đang có suffix biểu diễn nhị phân là:
suf_X = ababab

với Trường hợp:
+ Case 1 > Case 2: số X của ta sẽ thành 0[ababab].
-> giữ nguyên số lượng
+ Case 2 > Case 1: số X của ta sẽ thành 1[ababab].
-> giữ nguyên số lượng
+ Case 1 = Case 2: số X của ta có thể là 0[ababab] hoặc 1[ababab].
-> số lượng nhân đôi
*/
}

cout << ans << '\n' << number_of_X;

return 0;
}

:::
> [color=lightgreen]

:::success
:::    spoiler Hoặc code của @[SPyofgame](https://codeforces.com/profile/SPyofgame)

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;
int n, l, r, k;
int cnt[30][2];

bool in_range(int x)
{
return (l <= x) && (x <= r);
}

ll dfs_sum(int x = 0, int bit = 29)
{
if (bit < 0) return 0;

int k = 1 << bit;
int lt = (cnt[bit][0] > 0) && in_range(x | k) ? k : 0;
int rt = (cnt[bit][1] > 0) ? k : 0;
ll lv = 1LL * lt * cnt[bit][0];
ll rv = 1LL * rt * cnt[bit][1];

// cout << bit << " " << k << " " << x << " | " << lt << " " << rt << " | " << lv << " " << rv << endl;
if (lv > rv)
return dfs_sum(x | lt, bit - 1) + lv;
else
return dfs_sum(x | rt, bit - 1) + rv;
}

int dfs_cnt()
{
int res = 1;
for (int bit = 0; bit < 30; ++bit)
res <<= (cnt[bit][0] == cnt[bit][1]);

return res;
}

int main()
{
ios::sync_with_stdio(NULL);
cin.tie(NULL);
memset(cnt, 0, sizeof(cnt));

cin >> n >> l >> r >> k;
for (int i = 1; i <= n; ++i)
{
int x;
cin >> x;

for (int bit = 0; bit < 30; ++bit)
++cnt[bit][x >> bit & 1];
}

cout << dfs_sum() << "\n";
cout << dfs_cnt() << "\n";
return 0;
}

:::

-----
### Hướng dẫn subtask 3

Điểm khác biệt duy nhất giữa subtask này với subtask 2 là giới hạn của $L$ và $R$ không còn cố định.

Để giải quyết bài này ta cần biết đến kĩ thuật `DP-digit`, cụ thể là biết cách xử lý đồng thời hai giới hạn của hàm `DP-digit`.

lúc này ta vẫn dùng ma trận để minh họa:

a = {1, 4, 6, 5}
X = 5: 1010

a[0] : 1000 |a[0] ⊕ X : 0010
a[1] : 0010 -> |a[1] ⊕ X : 1000
a[2] : 0110 |a[2] ⊕ X : 1100
a[3] : 1010 |a[3] ⊕ X : 0000

Một cách làm có thể như sau:
* Chuyển cả $L$ và $L$ về dạng nhị phân.
* Ta định nghĩa `dp[pos][is_greater][is_smaller]` là một cặp tổng lớn nhất cho đoạn prefix kết thúc ở pos của bảng trên khi từng phần tử xor cho $X$ nằm trong đoạn $[L..R]$ và số lượng $X$ đã tạo ra kết quả đó.
* Lúc này, `is_greater = true` nếu ta đang xét $X$ lớn hơn $L$
* Lúc này, `is_smaller = true` nếu ta đang xét $X$ bé hơn $R$
* Phần tính tổng và đếm cũng tương tự subtask 2. 
* Khi này kết quả là sẽ là `dp[29][0][0]` với 29 là số lượng cột bit.

-----
### Code cho subtask 3

>***Tiền xử lý***: $O(N \times 29)$
>***Độ phức DP-digit***: $O(29 \times 2 \times 2)$
>***Độ phức tạp tổng***: $O(N \times 29 + 29 \times 2 \times 2) = O(N \times 29)$
>***Algo***: DP-digit, Bit Manipulation. 
> [color=lightgreen]

:::success
:::spoiler Code

#include <iostream>
#include <vector>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
using namespace std;
const long long lg = 30;

pii dp[lg][2][2];
ll n, k, L, R, cnt[lg];

vector <int> lower, upper; // hai cận

void convert(vector <int> &d, ll a){ //chuyển sang nhị phân
for (int i = 0; i < lg; i ++)
if (a & 1ll << i) d.push_back(1); else d.push_back(0);

}

pii cal(ll pos, bool is_greater, bool is_smaller){
if (pos < 0) return {0, 1};

pii &ans = dp[pos][is_greater][is_smaller];
if (ans.st != -1) return ans;

int upper_bound = upper[pos];
int lower_bound = lower[pos];

if (is_greater) lower_bound = 0;
if (is_smaller) upper_bound = 1;

ans = pii(-1, 0);

for (int i = lower_bound; i <= upper_bound; i ++){
bool new_g = is_greater;
bool new_s = is_smaller;

if (i > lower_bound) new_g = 1;
if (i < upper_bound) new_s = 1;

pii tmp = cal(pos - 1, new_g, new_s);

if (i == 1)
tmp.st += (n - cnt[pos])*(1ll << pos);
else
tmp.st += cnt[pos]*(1ll << pos);

if (tmp.st > ans.st)
ans = tmp;
else
if (ans.st == tmp.st)
ans.nd += tmp.nd;
}

// cout << ans.st << ' ' << ans.nd << '\n';

return ans;
}

int main(){
cin >> n >> L >> R >> k;

for (int i = 1, a; i <= n; i ++){
cin >> a;

for (int j = 0; j < lg; j ++)
if (a & 1ll << j) cnt[j] ++;
}

convert(lower, L);
convert(upper, R);

for (int i = 0; i < lg; i ++)
for (int j = 0; j < 2; j ++)
for (int t = 0; t < 2; t ++)
dp[i][j][t] = pii(-1, 0);

pii ans = cal(lg - 1, 0, 0);
cout << ans.st << '\n' << ans.nd;

}

:::

### Hướng dẫn subtask 4

Ở subtask 4 ta cũng xử lý dp gần như subtask 3, chỉ là ta thêm một chiều quản lý số dư của $X$ đang xét cho $K$.

Cụ thể ta sẽ có `dp[pos][is_greater][is_smaller][remain]` là một cặp tổng lớn nhất cho đoạn prefix kết thúc ở pos của bảng trên khi từng phần tử xor cho $X$ nằm trong đoạn $[L..R]$, với $X$ $mod$ $K=rem$, và số lượng $X$ đã tạo ra kết quả đó.

Đồng thời, ở đây có một `special subtask` khi mà $K$ lớn, cụ thể là $K \ge 10^{4}$. Vì ở đây số lượng $X$ có thể chia hết cho $K$ chỉ là $\frac{R - L}{k} \le 10^{5}$ nên ta hoàn toàn có thể brute từng $X$ và kết hợp với subtask 2 được cải tiến.

Từ đây, ta phân làm hai trường hợp:
- Nếu $K \le 10^{4}$: ta sẽ dùng DP-digit và kết quả sẽ là `dp[29][0][0][0]`.
- Nếu $K > 10^{4}$: ta sẽ duyệt qua từng $X$ chia hết cho $K$.

Phần code sẽ như sau.

----
### Code cho subtask 4

>***Tiền xử lý***: $O(N \times 29)$
>***Độ phức DP-digit***: $O(29 \times 2 \times 2)$
>***Độ phức tạp tổng***: $O(N \times 29 + 29 \times 2 \times 2) = O(N \times 29)$
>***Algo***: DP-digit, Bit Manipulation.
> [color=lightgreen]

:::success
:::spoiler Code

#include <iostream>
#include <vector>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
using namespace std;
const long long lg = 30;
const long long Max_rem = 1e4;
const long long N = 1e5 + 5;
pii dp[lg][2][2][Max_rem];
ll n, k, L, R, cnt[lg];

vector <int> lower, upper; // hai cận

void convert(vector <int> &d, ll a){ //chuyển sang nhị phân
for (int i = 0; i < lg; i ++)
if (a & 1ll << i) d.push_back(1); else d.push_back(0);

}

pii cal(ll pos, bool is_greater, bool is_smaller, int rem){
if (pos < 0){
if (rem == 0)
return {0, 1};
return {-5e9, 0};
}
pii &ans = dp[pos][is_greater][is_smaller][rem];
if (ans.st != -1) return ans;

int upper_bound = upper[pos];
int lower_bound = lower[pos];

if (is_greater) lower_bound = 0;
if (is_smaller) upper_bound = 1;

ans = pii(-5e9, 0);

for (int i = lower_bound; i <= upper_bound; i ++){
bool new_g = is_greater;
bool new_s = is_smaller;

if (i > lower_bound) new_g = 1;
if (i < upper_bound) new_s = 1;

pii tmp = cal(pos - 1, new_g, new_s, (rem + i*(1ll << pos))%k);

if (i == 1)
tmp.st += (n - cnt[pos])*(1ll << pos);
else
tmp.st += cnt[pos]*(1ll << pos);

if (tmp.st > ans.st)
ans = tmp;
else
if (ans.st == tmp.st)
ans.nd += tmp.nd;
}

// cout << ans.st << ' ' << ans.nd << '\n';

return ans;
}

ll get(ll x){ //subtask 2 sau khi cải tiến với X cố định
ll ans = 0;
for (ll i = 0; i < lg; i ++)
if (x & 1ll << i)
ans += (n - cnt[i])*(1ll << i);
else
ans += cnt[i]*(1ll << i);

return ans;
}

void special_subtask(){
ll ans = 0, cnt = 0;

for (ll X = 0; X <= R; X += k){
if (X < L) continue;
ll ans_for_cur_X = get(X);

if (ans_for_cur_X == ans)
cnt ++;
else if (ans_for_cur_X > ans)
ans = ans_for_cur_X, cnt = 1;

}

cout << ans << '\n' << cnt;

}

int main(){
cin >> n >> L >> R >> k;

for (int i = 1, a; i <= n; i ++){
cin >> a;

for (int j = 0; j < lg; j ++)
if (a & 1ll << j) cnt[j] ++;
}

if (k > Max_rem){
special_subtask();
return 0;
}

convert(lower, L);
convert(upper, R);

for (int i = 0; i < lg; i ++)
for (int j = 0; j < 2; j ++)
for (int t = 0; t < 2; t ++)
for (int rem = 0; rem < Max_rem; rem ++)
dp[i][j][t][rem] = pii(-1, 0);

pii ans = cal(lg - 1, 0, 0, 0);
cout << ans.st << '\n' << ans.nd;

}

:::