做电商网站电商公司,wordpress 添加目录,网站建设教育,全网关键词搜索工具背景
有一类问题和子集有关。 给你一个集合 S S S#xff0c;令 T T T 为 S S S 的超集#xff0c;也就是 S S S 所有子集的集合#xff0c;求 T T T 中所有元素的和。
暴力1
先预处理子集的元素和 A i A_i Ai#xff0c;再枚举子集。
for(int s0; s(1…背景
有一类问题和子集有关。 给你一个集合 S S S令 T T T 为 S S S 的超集也就是 S S S 所有子集的集合求 T T T 中所有元素的和。
暴力1
先预处理子集的元素和 A i A_i Ai再枚举子集。
for(int s0; s(1n); s)for(int i0; i(1n); i)if(si) f[s]A[i];时间复杂度 O ( n 4 ) O(n^4) O(n4)
暴力2
其实枚举子集有个小 trick
for(int s0; s(1n); s)for(int is; i0; i(i-1)s)f[s]A[i];由二项式定理时间复杂度为 O ( 3 n ) O(3^n) O(3n)
子集DP
令 g s , i g_{s,i} gs,i 为状态为 s s s只考虑后 i i i 位转移的答案。 那么转移就是 g s , i { g s , i − 1 s ( 1 i ) 0 g s , i − 1 g s ⨁ ( 1 i ) , i − 1 o t h e r w i s e g_{s,i} \begin{cases} g_{s,i-1} s\(1i)0 \\g_{s,i-1} g_{s\bigoplus(1i),i-1}otherwise\end{cases} gs,i{gs,i−1gs,i−1gs⨁(1i),i−1s(1i)0otherwise 这样可以做到不重不漏的转移。 推荐一篇blog非常形象https://www.cnblogs.com/maple276/p/17975253
可以发现这个转移只和上一层有关所以第二维是可以省略的。
前缀和子集向超集转移
for(int i0; in; i)
{for(int s0; s(1n); s){if(s_2)(f[s]f[s^_2])%(mod-1);}_21;
}后缀和超集向子集转移
for(int i0; in; i)
{for(int s0; s(1n); s){if(!(s_2))(f[s]f[s^_2])%(mod-1);}_21;
}差分
//后缀差分
for(int i0; i20; i)
{for(int s0; sS; s){if(!(s_2))(f[s]-f[s^_2])%mod;}_21;
}例题
CF165E
定义 x x x 和 y y y 相容为 x y 0 x\y0 xy0给你一个序列 A A A对于每个元素在 A A A 中找到和它相容的元素。 ∣ A ∣ ≤ 1 0 6 , A i ≤ 4 × 1 0 6 |A|\leq 10^6,A_i\leq 4\times 10^6 ∣A∣≤106,Ai≤4×106
思路 x y 0 x\y0 xy0 等价于 x ˜ y y \~x\yy x˜yy那么只需要对 A A A做类似前缀和的操作加法改成覆盖即可。
代码
#includebits/stdc.h
#define int long long
using namespace std;
const int S122;
void O_o()
{int n;cinn;vectorint f(S,-1),a(n1);for(int i1; in; i){cina[i];f[a[i]]a[i];}int _21;for(int i0; i21; i){for(int s0; sS; s){if(!(s_2)) continue;if(f[s^_2]!-1)f[s]f[s^_2];}_21;}int tS-1;for(int i1; in; i){coutf[t^a[i]] ;}cout\n;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);coutfixedsetprecision(2);int T1;
// cinT;while(T--){O_o();}
}
