Chiori and Doll Picking (hard version)
For every k from 0 to m, count how many subsets have xor with exactly k set bits.
Problem Summary
Original task summary for this archive page. The official Codeforces statement is linked in the header instead of being mirrored here.
You are given \(n\) integers, each using at most \(m\) bits. For every \(k \in [0,m]\), count how many subsets have xor value with exactly \(k\) ones in binary. The answer is required modulo \(998244353\).
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Motivation
The direct search space is \(2^n\), so counting subsets one by one is not an option.
The real object to count is not the subsets themselves, but the xor values they can produce. Once the set of reachable xor values is understood, the subset counts follow from linear algebra.
Key Observations
If the xor-basis rank is \(r\), then the reachable xor values form an \(r\)-dimensional vector space \(V \subseteq \mathbb{F}_2^m\).
Every reachable xor value appears the same number of times: exactly \(2^{n-r}\) subsets produce it.
So the task becomes: for each Hamming weight \(k\), how many vectors in \(V\) have weight \(k\)?
Because \(m \le 53\), either the rank \(r\) or the corank \(m-r\) is at most \(26\). That is the threshold that makes enumeration practical.
Derivation
Reduce the input numbers to a xor basis and then push it into reduced row-echelon form over \(\mathbb{F}_2\). Let the pivot columns be \(P\) and the free columns be \(F\).
If we reorder coordinates so the pivot columns come first, the basis becomes a generator matrix of the form \[ G = [I_r \mid M]. \] This gives two cases.
Case 1: \(r \le 26\).
Enumerate all \(2^r\) linear combinations of the basis rows. Each combination is one reachable xor value, so we can count its popcount directly.
Case 2: \(m-r \le 26\).
Enumerating the whole code is too expensive, but the dual code is small. For \[ G = [I_r \mid M], \] a generator matrix for the dual code is \[ H = [M^T \mid I_{m-r}]. \] Now enumerate all dual codewords instead.
Let \(A_i\) be the number of codewords in \(V\) with weight \(i\), and let \(B_j\) be the number of dual codewords with weight \(j\). The MacWilliams identity for binary linear codes gives \[ A_i = \frac{1}{2^{m-r}} \sum_{j=0}^{m} B_j K_i(j), \] where \[ K_i(j) = \sum_t (-1)^t \binom{j}{t}\binom{m-j}{i-t} \] is the binary Krawtchouk polynomial.
So once the dual weight distribution is known, the primal weight distribution follows.
Algorithm
Build a xor basis from the input numbers and convert it to reduced row-echelon form.
Let \(r\) be the rank.
If \(r \le 26\), enumerate all codewords of the span and count them by popcount.
Otherwise construct a basis of the dual code from the free columns, enumerate all dual codewords, and recover the primal weight distribution with the MacWilliams formula.
Multiply every count by \(2^{n-r}\), because each reachable xor value comes from that many subsets.
Why It Works
The xor basis captures exactly the reachable xor values. Row reduction does not change that vector space, it only puts it into a form where either the space itself or its dual can be enumerated efficiently.
The constant factor \(2^{n-r}\) is standard: the map from subsets to xor values is a linear map from \(\mathbb{F}_2^n\) onto an \(r\)-dimensional image, so every image point has a kernel-sized preimage of size \(2^{n-r}\).
In the large-rank case, the MacWilliams identity is the exact bridge between the weight distribution of a binary linear code and the weight distribution of its dual. That is why enumerating the dual is enough.
Pseudocode
Natural algorithm flow before the concrete implementation.
Read \(n\) and \(m\).
Build a xor basis of the input numbers. Convert the basis to reduced row-echelon form. Let \(r\) be the rank.
If \(r \le 26\):
enumerate all \(2^r\) xor combinations of the basis rows
count how many results have each popcount
Otherwise:
construct the dual basis from the free columns
enumerate all \(2^{m-r}\) dual codewords
count dual weights
recover primal weights with the MacWilliams formula
Multiply every weight count by \(2^{n-r}\). Print the \(m+1\) answers.
Complexity Analysis
Time and memory costs for the exact implementation shown below.
Basis construction and row reduction: \(O(nm + m^2)\)
Enumeration: \(O(2^{\min(r,\,m-r)})\)
MacWilliams recovery in the large-rank case: \(O(m^3)\), which is tiny here because \(m \le 53\)
Memory: \(O(m^2)\) outside the temporary enumeration counters
C++ Solution
The exact repository source used for this solution page.
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int MOD = 998244353;
int mod_pow(int base, int exponent) {
int result = 1;
while (exponent > 0) {
if (exponent & 1) {
result = int(1LL * result * base % MOD);
}
base = int(1LL * base * base % MOD);
exponent >>= 1;
}
return result;
}
vector<int> enumerate_weight_distribution(const vector<unsigned long long>& basis, int m) {
const int dimension = int(basis.size());
const uint32_t total = 1u << dimension;
vector<int> counts(m + 1, 0);
unsigned long long current = 0;
uint32_t previous_gray = 0;
for (uint32_t mask = 0; mask < total; ++mask) {
const uint32_t gray = mask ^ (mask >> 1);
if (mask != 0) {
const uint32_t diff = gray ^ previous_gray;
const int changed_bit = __builtin_ctz(diff);
current ^= basis[changed_bit];
}
++counts[__builtin_popcountll(current)];
previous_gray = gray;
}
return counts;
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<unsigned long long> pivot_basis(m, 0);
for (int i = 0; i < n; ++i) {
unsigned long long value;
cin >> value;
for (int bit = m - 1; bit >= 0; --bit) {
if (((value >> bit) & 1ULL) == 0) {
continue;
}
if (pivot_basis[bit] == 0) {
pivot_basis[bit] = value;
break;
}
value ^= pivot_basis[bit];
}
}
for (int bit = 0; bit < m; ++bit) {
if (pivot_basis[bit] == 0) {
continue;
}
for (int lower = 0; lower < bit; ++lower) {
if ((pivot_basis[bit] >> lower) & 1ULL) {
pivot_basis[bit] ^= pivot_basis[lower];
}
}
}
for (int bit = 0; bit < m; ++bit) {
if (pivot_basis[bit] == 0) {
continue;
}
for (int higher = bit + 1; higher < m; ++higher) {
if ((pivot_basis[higher] >> bit) & 1ULL) {
pivot_basis[higher] ^= pivot_basis[bit];
}
}
}
vector<int> pivot_columns;
vector<unsigned long long> basis_rows;
vector<char> is_pivot(m, false);
for (int bit = 0; bit < m; ++bit) {
if (pivot_basis[bit] == 0) {
continue;
}
is_pivot[bit] = true;
pivot_columns.push_back(bit);
basis_rows.push_back(pivot_basis[bit]);
}
const int rank = int(basis_rows.size());
const int subset_multiplier = mod_pow(2, n - rank);
vector<int> answer(m + 1, 0);
if (rank <= 26) {
const vector<int> codeword_counts = enumerate_weight_distribution(basis_rows, m);
for (int weight = 0; weight <= m; ++weight) {
answer[weight] = int(1LL * codeword_counts[weight] * subset_multiplier % MOD);
}
} else {
vector<int> free_columns;
for (int bit = 0; bit < m; ++bit) {
if (!is_pivot[bit]) {
free_columns.push_back(bit);
}
}
vector<unsigned long long> dual_basis;
dual_basis.reserve(free_columns.size());
for (int free_column : free_columns) {
unsigned long long vector_mask = 1ULL << free_column;
for (int row = 0; row < rank; ++row) {
if ((basis_rows[row] >> free_column) & 1ULL) {
vector_mask |= 1ULL << pivot_columns[row];
}
}
dual_basis.push_back(vector_mask);
}
const vector<int> dual_counts = enumerate_weight_distribution(dual_basis, m);
vector<vector<int>> combinations(m + 1, vector<int>(m + 1, 0));
for (int i = 0; i <= m; ++i) {
combinations[i][0] = 1;
for (int j = 1; j <= i; ++j) {
combinations[i][j] = combinations[i - 1][j - 1];
if (j < i) {
combinations[i][j] += combinations[i - 1][j];
if (combinations[i][j] >= MOD) {
combinations[i][j] -= MOD;
}
}
}
}
const int inverse_dual_size = mod_pow(mod_pow(2, m - rank), MOD - 2);
for (int target_weight = 0; target_weight <= m; ++target_weight) {
long long total = 0;
for (int dual_weight = 0; dual_weight <= m; ++dual_weight) {
if (dual_counts[dual_weight] == 0) {
continue;
}
long long coefficient = 0;
const int low = max(0, target_weight - (m - dual_weight));
const int high = min(target_weight, dual_weight);
for (int take = low; take <= high; ++take) {
long long ways = 1LL * combinations[dual_weight][take] *
combinations[m - dual_weight][target_weight - take] % MOD;
if (take & 1) {
coefficient -= ways;
} else {
coefficient += ways;
}
}
coefficient %= MOD;
if (coefficient < 0) {
coefficient += MOD;
}
total += coefficient * dual_counts[dual_weight];
total %= MOD;
}
answer[target_weight] = int(total * inverse_dual_size % MOD);
answer[target_weight] = int(1LL * answer[target_weight] * subset_multiplier % MOD);
}
}
for (int weight = 0; weight <= m; ++weight) {
cout << answer[weight] << (weight == m ? '\n' : ' ');
}
return 0;
}
Pitfalls
Edge cases and implementation traps worth checking before reusing the idea in contest code.
Use a 64-bit unsigned integer for the bitmasks. \(m \le 53\), so every codeword fits safely.
Gray-code enumeration is a good fit here because only one basis vector changes between consecutive states.
The modulo division by \(2^{m-r}\) is handled with modular inverses, not integer division.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/codeforces/3500/problems/chiori-and-doll-picking-hard-version/editorial.texC++ implementationcompetitive_programming/codeforces/3500/problems/chiori-and-doll-picking-hard-version/solution.cppMetadatacompetitive_programming/codeforces/3500/problems/chiori-and-doll-picking-hard-version/meta.json