[ Nowcoder Contest 167 #C ] 部分和

\(\\\)

\(Description\)

给出一个长度为\(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<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 1<<21

#define R register

#define gc getchar

using 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<n;++i) a[i]=rd();

  for(R int i=0;i<=lim;++i){

    ll now=1<<i;

    for(R int j=0;j<n;++j)

      if(j&now) a[j]+=a[j^now];

  }

  for(R int i=0;i<n;++i) printf("%lld\n",a[i]);

  return 0;

}

巴特西

[ Nowcoder Contest 167 #C ] 部分和

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章