Official Editorial (C++)

Explanation

We can first precompute the wu values for each pair of strings. Then, we can sum up the number of strings that gives each wu value of each string in a prefix sum (represented by pref_wu in the following implementation). Thus, for each query, we can utilize the output of our prefix sum array.

In the implementation, instead of looping through all bits and finding which bits are the same, $i \oplus j$ essentially gives the mask of the bits that are different, so wu of total minus wu of $(i \oplus j)$ will also give wu values of the bits that are the same. Also, since $k$ is at most $100$, we can precompute the answer for every $k$ for each string.

Implementation

Time Complexity: $\mathcal{O}({2^{2n}} + qn)$

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

const int MAX_K = 100;

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> w(n);
	for (int &i : w) { cin >> i; }

Copy
import java.io.*;
import java.util.*;

public class TheWu {
	public final static int MAX_K = 100;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());