D. The Wu

Wu score ( s, t ) = Sum of w[i] ( s[i] == t[i] && 1<=i<=n )

모든 비트의 길이가 n이고 s 위치에 올 수 있는 비트 m개, 쿼리의 개수 q가 주어질 때 쿼리에 답하는 문제다.

쿼리에는 t maximum_score 순으로 주어지며 

Wu score ( {s}, t ) <= maximum_score 를 만족하게 하는 s의 개수를 세는 문제다.

1.

s가 m개 주어지지만 비트의 길이가 12까지라 1<<12개밖에 없으며 비트가 같으면 연산 결과도 같다.

따라서 m개의 비트를 모두 저장하는게 아니라 개수만 세어주면 된다.

2.

쿼리가 50만개이므로 사전에 미리 모든 답을 구해놓고 쿼리에 답하는 방법을 사용했다.

0 < i < 1<<n, 0 < j < 1<<n

범위를 모두 돌면서 i,j에서 같은 위치에 같은 비트를 찾고 해당 위치에 따른 점수를 합산한 다음

이걸 배열에 저장한다. 그리고 누적합을 구한다.

#include <iostream>
using namespace std;
 
typedef long long ll;
 
int N, M, Q;
int cnt[1 << 12];
int d[1 << 12][1201];
int p[1 << 12];
char temp[13];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M >> Q;
    for (int i = 0; i < N; ++i) {
        cin >> p[1 << i];
    }
    for (int i = 0, b; i < M; ++i) {
        b = 0;
        cin >> temp;
        for (int j = 0; j < N; ++j)
            b += (temp[j] - '0') << j;
        cnt[b]++;
    }
    for (int i = 0; i < 1 << N; ++i) {
        for (int j = 0; j < 1 << N; ++j) {
            int c = ~(i ^ j)&((1 << N) - 1);
            int sum = 0;
            for (int temp = c; temp; temp -= temp & -temp) {
                sum += p[temp&-temp];
            }
            d[i][sum] += cnt[j];
        }
    }
    for (int i = 0; i < 1 << N; ++i) {
        for (int j = 1; j < 101; ++j)
            d[i][j] += d[i][j - 1];
    }
    while (Q--) {
        int b = 0, tt;
        cin >> temp >> tt;
 
        for (int j = 0; j < N; ++j)
            b += (temp[j] - '0') << j;
 
        cout << d[b][tt] << '\n';
    }
    return 0;
}