重新学习。。。
0.引入
考虑求子集和 $b(i)=\sum_{j|i=i} a(j)$ ？我们直接暴力枚举子集是 $\mathcal O(3^n)$。但是利用 FMT 相同的，高维前缀和：具体的，我们对于二进制的每一位都做一遍前缀和，我们就可以做到 $\mathcal O(n2^n)$。子集会利用这种类似思想。
1.算法介绍
类似于高维前缀和的思想，我们分别对于前 $i$ 位进行 DP。
2.例题
高维前缀和模板题。要使得 $x\&y=0$，我们相当于在前缀和里查找 $x$ 的补集即可得到 $y$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10,M=22,S=1<<M;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N];
int f[1<<M];
int main()
{
memset(f,-1,sizeof(f));
read(n);
for(int i=1;i<=n;i++)
{
read(a[i]);
f[a[i]]=a[i];
}
for(int i=0;i<M;i++)
for(int s=0;s<S;s++)
if(s>>i&1)
f[s]=max(f[s],f[s^(1<<i)]);
for(int i=1;i<=n;i++)
printf("%d ",f[(S-1)&(~a[i])]);
return 0;
}
|