\(\\\)

---

给出一个长度为\(N\)的数组\(A[i]\)，保证\(N\)为 \(2\) 的整次幂。

对于每个 \(i\ (i\in [0,N))\)求所有满足\((i\ \&\ j) == j\) 的\(A[j]\)之和。

• \(N\in [1,2^{20}]\)，\(A[i]\in [1,10^3]\)。

\(\\\)

\(Solution\)

---

考虑每一个\(i\)的答案。

将 \(i\) 按照二进制位分解，那么它的答案就是所有子集的答案。

换句话说，设一共有\(K\)个二进制位，建立数组 \(f[2][2][2][2]....[2]\)分别表示每一位的情况，那么有

\[ f[c_1][c_2]...[c_k]=\sum_{d_1=0}^{c_1}\sum_{d_2=0}^{c_2}...\sum_{d_k=0}^{c_k}A[d_1][d_2]...[d_k] \]

此时\(A\)数组的下标是将原来的十进制数按二进制位分解得到的数。

我们发现这是一个\(K\)维前缀和，因为它是一个子集求和。

然后题解就安利了一个“快速莫比乌斯变换”，其实是另一种高维求前缀和的方法。

一般求二维前缀和我们都是容斥做法，其实还可以每一行先求和，每一列再求和。

这个一样，从低到高按位求和即可，注意只会加上当前一位不同的答案，因为前面固定，后面更小的子集已经在当前要加的对象上累加过一次了。

因为只有两个数所以直接压成一维即可。

\(\\\)

\(Code\)

---

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 1<<21#define R register#define gc getcharusing namespace std;typedef long long ll; ll n,lim,a[N]; inline ll rd(){ ll x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;} int main(){ n=rd(); lim=min(20ll,(ll)log2(n)+1); for(R int i=0;i