虽然m有5*10^5个但是状态最多有4096个 所以可以暴力匹配 找到 状态x与其他状态的匹配价值
然后记录每个状态的价值在100以内的每个价值所包含的串的数目 查询时将所有小于等于k的加和即为结果
比赛最后才想出来。。。。傻了
#include <iostream>
using namespace std;
const int N = 5e5 + 10, M = 4100;
char s[N];
int w[20];
int nums[N];
int cnt[M][110];
int sum[M];
int n, m, q;
int get(char *s){
int res = 0;
for (int i = n; i; i--){
if(s[i] == '1') res += 1 << (n - i);
}
return res;
}
int main(){
scanf("%d%d%d", &n, &m, &q);
for (int i = 0; i < n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= m; i++){
scanf("%s", s + 1);
nums[get(s)]++;
}
int M = 1 << n;
for (int i = 0; i < M; i++){
for (int j = 0; j < n; j++){
if(i >> j & 1){
sum[i] += w[n - 1 - j];
if(sum[i] > 100) sum[i] = 101;
}
}
}
for (int i = 0; i < M; i++){
for (int j = 0; j < M; j++){
cnt[i][sum[M - 1 - (i ^ j)]] += nums[j];
}
}
while(q--){
int k;
scanf("%s", s + 1);
scanf("%d", &k);
int num = get(s);
int res = 0;
for (int i = 0; i <= k; i++){
res += cnt[num][i];
}
printf("%d\n", res);
}
return 0;
}