The Wu

Explicación

Primero podemos precomputar los valores wu de cada par de strings. Luego, sumamos la cantidad de strings que dan cada valor wu de cada string en una suma de prefijos (representada por pref_wu en la implementación siguiente). Así, para cada consulta, podemos usar la salida de nuestro arreglo de sumas de prefijos.

En la implementación, en lugar de recorrer todos los bits y hallar cuáles son iguales, $i \oplus j$ da esencialmente la máscara de los bits que son distintos, así que wu del total menos wu de $(i \oplus j)$ también dará los valores wu de los bits que son iguales. Además, como $k$ es a lo sumo $100$ , podemos precomputar la respuesta para cada $k$ de cada string.

Implementación

Complejidad temporal: $\mathcal{O}({2^{2n}} + qn)$

C++Java


#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; }
 
	// precomputamos el valor wu de cada subconjunto
	vector<int> wu(1 << n);
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) { wu[i] += w[j]; }
		}
	}
 
	// convertimos todos los strings a enteros y guardamos el conteo
	vector<int> str_count(1 << n);
	for (int i = 0; i < m; i++) {
		string s;
		cin >> s;
		int val = 0;
		for (int j = 0; j < n; j++) {
			if (s[j] == '1') { val += 1 << j; }
		}
		str_count[val]++;
	}
 
	/*
	 * precomputamos el valor wu de cada k posible para un string
	 * pref_wu[i][j] guarda el prefijo del conteo hasta k = j para el string i
	 */
	vector<vector<int>> pref_wu(1 << n, vector<int>(MAX_K + 1));
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < (1 << n); j++) {
			int all_same = (1 << n) - 1;
			int diff = i ^ j;
			int wu_value = wu[all_same] - wu[diff];
			if (wu_value <= MAX_K) { pref_wu[i][wu_value] += str_count[j]; }
		}
		// acumulamos sumas de prefijos del conteo
		for (int j = 1; j <= MAX_K; j++) { pref_wu[i][j] += pref_wu[i][j - 1]; }
	}
 
	for (int query = 0; query < q; query++) {
		string t;
		int k;
		cin >> t >> k;
		int val = 0;
		for (int i = 0; i < n; i++) {
			if (t[i] == '1') { val += 1 << i; }
		}
		cout << pref_wu[val][k] << "\n";
	}
}


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());
		int m = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		int[] w = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { w[i] = Integer.parseInt(st.nextToken()); }
 
		// precomputamos el valor wu de cada subconjunto
		int[] wu = new int[1 << n];
		for (int i = 0; i < (1 << n); i++) {
			for (int j = 0; j < n; j++) {
				if ((i & (1 << j)) != 0) { wu[i] += w[j]; }
			}
		}
 
		// convertimos todos los strings a enteros y guardamos el conteo
		int[] strCount = new int[1 << n];
		for (int i = 0; i < m; i++) {
			String s = br.readLine();
			int val = 0;
			for (int j = 0; j < n; j++) {
				if (s.charAt(j) == '1') { val += 1 << j; }
			}
			strCount[val]++;
		}
 
		/*
		 * precomputamos el valor wu de cada k posible para un string
		 * prefWu[i][j] guarda el prefijo del conteo hasta k = j para el string i
		 */
		int[][] prefWu = new int[1 << n][MAX_K + 1];
		for (int i = 0; i < (1 << n); i++) {
			for (int j = 0; j < (1 << n); j++) {
				int allSame = (1 << n) - 1;
				int diff = i ^ j;
				int wuValue = wu[allSame] - wu[diff];
				if (wuValue <= MAX_K) { prefWu[i][wuValue] += strCount[j]; }
			}
			// acumulamos sumas de prefijos del conteo
			for (int j = 1; j <= MAX_K; j++) { prefWu[i][j] += prefWu[i][j - 1]; }
		}
 
		for (int query = 0; query < q; query++) {
			st = new StringTokenizer(br.readLine());
			String t = st.nextToken();
			int k = Integer.parseInt(st.nextToken());
			int val = 0;
			for (int i = 0; i < n; i++) {
				if (t.charAt(i) == '1') { val += 1 << i; }
			}
			System.out.println(prefWu[val][k]);
		}
	}
}