cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2023 · MediumBitwise subarray counting

Rectangle XOR Sum

National Olympiad — Regional round (2023 season)

Submission name: sum.cpp

Solve in Editor →

Problem summary

Compute the sum of XOR values of all nonempty rectangular submatrices of a given table.

Input

m and n, then m rows of n nonnegative integers.

Output

The sum over all rectangular submatrices.

Constraints

1 < m,n < 300; 0 ≤ a[i][j] < 10000.

Worked example

An independently prepared example for this explanation.

Input

2 2
5 2
1 6

Output

36

Solution analysis

  1. Fix the top and bottom rows. XOR each column between those rows to obtain a one-dimensional array. Every contiguous subarray of this collapsed row corresponds to exactly one rectangle with the chosen row boundaries.
  2. For each bit from 0 through 13, scan prefix XORs of the collapsed row. A subarray has this bit set exactly when its two prefix bits differ. Count earlier prefixes of the opposite bit and add their number times 2^bit. Initialize one zero prefix.
  3. For the sample, the top row contributes 5+2+(5 XOR 2)=14, the bottom row contributes 1+6+7=14, and the two-row collapse [4,4] contributes 4+4+0=8. The total is 36.

Why it works

Choosing a row pair and a column interval uniquely describes a rectangle, whose XOR equals the corresponding collapsed subarray XOR. Prefix cancellation identifies exactly the set bits of each subarray XOR. Counting opposite prefix bits for every endpoint counts each rectangle’s bit contribution exactly once, and summing weighted bits reconstructs its value.

Complexity: O(m^2*n*14) time and O(m*n+n) space.

Watch out. Reset the collapsed columns for every new top row and retain them while extending the bottom. Include the empty prefix for each scan. The final sum requires 64-bit arithmetic.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
// Algorithm: Fix the top and bottom rows.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows,columns;
    cin>>rows>>columns;
    vector<vector<int>>table(rows,vector<int>(columns));
    for(auto&row:table){
        for(int&value:row){
            cin>>value;
        }
    }
    long long answer=0;
    for(int top=0;top<rows;++top){
        vector<int>collapsed(columns,0);
        for(int bottom=top;bottom<rows;++bottom){
            for(int column=0;column<columns;++column){
                collapsed[column]^=table[bottom][column];
            }
            for(int bit=0;bit<14;++bit){
                long long count[2]={1,0};
                int parity=0;
                for(int value:collapsed){
                    parity^=(value>>bit)&1;
                    answer+=count[1-parity]*(1LL<<bit);
                    ++count[parity];
                }
            }
        }
    }
    cout<<answer<<'\n';
}

Source: Arena Olimpiici ↗