Subset Sum 3
仍然是有 \(N\) 个数 \(A_i\)，仍然是要求子集数量使得子集里面的数的和为 \(X\)。
让我给你看看范围：
\(1 \le N \le \color{Red}{40}\)
dp！
\(1 \le A_i \le \color{Red}{10^9}\)
Uhhh......
（By Graph_editor）
如图，在起点和终点已知的情况下，我们可以起点捜一半，终点捜一半，再将两部分的答案合并起来。
这个题也是一样的，起点捜一半，终点捜一半，然后开个 map 合并起来。
（*** 卡了我好久的常数）
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x, t[44], ans;
vector<int> v;
void DFS1(int cur, int cnt) {
if(cnt > x) {
return ;
}
if(cur > n / 2) {
v.push_back(cnt);
return ;
}
DFS1(cur + 1, cnt);
DFS1(cur + 1, cnt + t[cur]);
}
void DFS2(int cur, int cnt) {
if(cnt > x) {
return ;
}
if(cur <= n / 2) {
auto p = equal_range(v.begin(), v.end(), x - cnt);
ans += p.second - p.first;
return ;
}
DFS2(cur - 1, cnt);
DFS2(cur - 1, cnt + t[cur]);
}
signed main() {
cin >> n >> x;
for(int i = 1; i <= n; i++) {
cin >> t[i];
}
DFS1(1, 0);
sort(v.begin(), v.end());
DFS2(n, 0);
cout << ans << '\n';
return 0;
}
路径计数 1145141919810
我们有一个网格。
这个网格是 \(N \times M\) 的，每一个格子 \((i, j)\) 有一个权值 \(A_{i, j}\)。
有多少条 \((1, 1)\) 到 \((N, M)\) 的路径满足路径上格子的权值异或和为 \(K\)？
解法
我们搜到路径的一半，不捜了。
剩下一半我们从终点开始捜，扫到路径的一般记录答案。
然后没了。
#include <bits/stdc++.h>
using namespace std;
const int kLm = 20;
int n, m;
vector<long long> v[22][22];
long long arr[22][22], k, ans;
void DFS1(int x, int y, long long r, int c) {
if(c == (n + m - 2) / 2) {
v[x][y].push_back(r);
return ;
}
DFS1(x + 1, y, r ^ arr[x + 1][y], c + 1);
DFS1(x, y + 1, r ^ arr[x][y + 1], c + 1);
}
void DFS2(int x, int y, long long r, int c) {
if(c <= (n + m - 2) / 2) {
auto p = equal_range(v[x][y].begin(), v[x][y].end(), k ^ r);
ans += p.second - p.first;
return ;
}
DFS2(x - 1, y, r ^ arr[x][y], c - 1);
DFS2(x, y - 1, r ^ arr[x][y], c - 1);
}
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
DFS1(1, 1, arr[1][1], 0);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sort(v[i][j].begin(), v[i][j].end());
}
}
DFS2(n, m, 0, n + m - 2);
cout << ans << '\n';
return 0;
}