1 条题解
-
0
60pts
首先可以把所有元素都进行与运算,得到一个结果 ,把所有集合内的元素和 进行异或运算,这样答案不变,使得所有元素与运算的结果为 。
接下来用 ,表示所有包含 这一位的集合 内的所有数与运算的结果,可以发现,答案一定是 每个数取或不取,或运算得到的结果去重。
进一步转化,问题等价于如果对于一对 ,满足 中所有 被 包含,那么 不能同时选,问方案数。
问题等价于给定一个 个点的图,有连边的点不能同时选,问选择的方案数。
当 个点时,如果一个点是孤立点,那么直接忽略,把答案乘 ,否则任取一个点选或不选,如果不选变成 的子问题,如果选至少有额外一个点不能选,变成至少 的子问题,复杂度为 ,为斐波那契的第 项,数据没有卡的特别慢,这种做法在常数优秀的情况下也能通过 分。
100pts
考虑枚举前 个点选或不选,就能知道剩下 个点是否可以选。
我们先预处理出后 个点 种情况做判定,利用高维前缀和算出所有可能情况的答案,然后利用meet in the middle,枚举前 个点的情况,直接计算即可。
复杂度为 。
#include<bits/stdc++.h> using namespace std; const int K = 40; const int KEK = 1 << 23; long long memo[KEK + 228]; long long calc_dp(long long mask, vector<long long>& inside) { if (mask < KEK && memo[mask]) { return memo[mask]; } int mx_bit = 63 - __builtin_clzll(mask); long long ans = calc_dp((mask ^ (1ll << mx_bit)) & (~inside[mx_bit]), inside) + calc_dp(mask ^ (1ll << mx_bit), inside); if (mask < KEK) memo[mask] = ans; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector<long long> A(n); for (int i = 0; i < n; ++i) cin >> A[i]; long long total_and = (1ll << K) - 1; for (int i = 0; i < n; ++i) total_and &= A[i]; for (int i = 0; i < n; ++i) A[i] ^= total_and; vector<long long> ands(K); for (long long x : A) { for (int i = 0; i < K; ++i) { if (x & (1ll << i)) { if (ands[i] != 0) ands[i] &= x; else ands[i] = x; } } } vector<long long> vals; for (int i = 0; i < K; ++i) { if (ands[i]) vals.emplace_back(ands[i]); } sort(vals.begin(), vals.end()); vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); int m = vals.size(); vector<long long> inside(m); for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { if ((vals[i] & vals[j]) == vals[i]) inside[j] |= 1ll << i; } } memo[0] = 1; cout << calc_dp((1ll << m) - 1, inside) << '\n'; return 0; }
- 1
信息
- ID
- 226
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者