位运算+前缀和+预处理，CF 1017D - The Wu
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
1017D - The Wu
二、解题报告
1、思路分析
我们注意到 sum(w[])会很大但是 k 很小，这说明我们可以从k的值域入手
又观察到 n 很小，有点状压预处理的意思
因为n <= 12，我们可以预处理：
cnt[x], x < 1 << n，cnt[x] 为 x 出现次数
sum[x]，x < 1 << n，当 s 和 t 相同位 = x时的花费
acc[k][t]，和 t 相同位 花费不超过k的s的数目
这个如何预处理呢？
我们直接暴力枚举所有s和t的可能，两两之间通过 ((1 << n) - 1) ^ (s ^ t) 即可得到相同位的集合，进而得到花费，然后对花费求前缀和即可
2、复杂度
时间复杂度： O(2^{2n} + 2^n U + qn)空间复杂度：O(n + m)
3、代码详解
#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1'000'000'007;void solve() {int n, m, q;std::cin >> n >> m >> q;std::vector<int> w(n), cnt(1 << n);for (int i = 0; i < n; ++ i) std::cin >> w[i];std::vector<int> sum(1 << n);for (int i = 1, ed = 1 << n; i < ed; ++ i) {int lb = (i & -i);sum[i] = sum[i ^ lb] + w[n - 32 + __builtin_clz(lb)];}std::string s;for (int i = 0; i < m; ++ i) {std::cin >> s;int num = 0;for (int j = 0; j < n; ++ j)if (s[n - 1 - j] ^ 48)num |= 1 << j;++ cnt[num];}std::vector<std::vector<int>> acc(101, std::vector<int>(1 << n));int msk = (1 << n) - 1;for (int i = 0, ed = 1 << n; i < ed; ++ i) {for (int j = 0, ed = 1 << n; j < ed; ++ j) {if (sum[msk ^ (i ^ j)] <= 100)acc[sum[msk ^ (i ^ j)]][i] += cnt[j];}for (int j = 0; j < 100; ++ j)acc[j + 1][i] += acc[j][i];}std::string t;for (int i = 0, k; i < q; ++ i) {std::cin >> t >> k;int num = 0;for (int j = 0; j < n; ++ j)if (t[n - 1 - j] ^ 48)num |= 1 << j;std::cout << acc[k][num] << '\n';}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}return 0;
}