\(Description：\)

给出长为n的序列，有n个元素\(a_i\)，求出对于每个i的\(\sum_{i\&j=j}a_j\)

\(Sample\) \(Input:\)

8

1

2

4

8

16

32

64

128

\(Sample\) \(Output:\)

1

3

5

15

17

51

85

255

\(Solution:\)

这题一眼还是容斥啊，真糟糕。。。

突然发现题面告诉我容斥是个**

题面提示里面告诉我们要求前缀和，要一维一维求，不然容斥项数太多对复杂度影响大。

那么发现了前缀和这个词，考虑一下这个鬼东西。

欧，好像有点道理，考虑给出的转移条件 \(i\&j=j\)

这不就告诉我们 \(j\) 是 \(i\) 的二进制子集么？

那么只要当前的 \(i\) 枚举出他的子集就可以了，枚举子集时发现这个枚举其实和前缀和思想很像

就是把一位的 \(1\) 消掉，那么考虑一种睿智的做法：

弄一个二十一维的前缀和数组。。。

当然也可以状压！

不过若想写400行，我也拦不住嘛，对不对？

只能说：

可以呀，孙贼，你挺会玩儿啊！

开个玩笑，开个玩笑，别打我呀~~，别别别——————————————————啊！

其实这算法啊还有一个名字——

FMT

这里就不讲了，我先去搬搬LG的博客。

#include
    
     using namespace std;int n;const int N=(1<<21),M=1000;#define dd s=getchar()inline int rd(){    int f=1,x=0;char dd;    while(!isdigit(s)) { if(s=='-')f=-1;dd;}    while(isdigit(s))  { x=(x<<1)+(x<<3)+(s^48);dd;}    return x*f;}#undef dd #define dd putcharinline void wrt(int x){    if(x<0) dd('-'),x=-x;    if(x>9) wrt(x/10);    dd(x%10^48);}int a[N+5],ans[N+5];inline void FMT(int *f){    for(int j=0;j<=21;++j) for(int i=0;i