高速ゼータ変換を知っていますか？

はじめに

高速ゼータ変換、名前いかついですよね。
実は次元の高い累積和みたいなことをやっているだけです。

高速ゼータ変換とは

$${2^n}$$個のデータ$${A_0…A_{2^n-1}}$$があります。
各$${0\le i\le 2^n-1}$$について、$${j }$$の立っているbitが$${i}$$にも立っているようなすべての$${j}$$についての$${A_j}$$を考え、それらすべての演算(足し算や最小最大など)結果を$${B_i}$$とします。
この$${B_i}$$全体を$${O(n*2^n)}$$の計算量で求めるのが高速ゼータ変換です。

やりかた

初めに$${B_i=A_i}$$とします。
あるbit(下から0スタートで$${i}$$桁目)に注目し、そのbitが立っている数$${x}$$を見つけたら$${B_{x}+=B_{x-2^i}}$$を行います(累積和ポイント)。
ここで、今回は和で書きましたが、最小ならminのように適宜変えてください。
上記の操作をすべてのbitで行えば完了です。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int n;

int main() {
    cin>>n;
    vector<long long int>A((1<<n));
    for (long long int i = 0; i < (1<<n); i++)
    {
        cin>>A[i];
    }
    vector<long long int>B=A;
    //高速ゼータ変換
    for (long long int i = 0; i < n; i++)
    {
        for (long long int x = 0; x < (1<<n); x++)
        {
            //i番目のbitが立っている
            if(x&(1<<i)){
                B[x]+=B[x-(1<<i)];
            }
        }
    }
    for (long long int i = 0; i < (1<<n); i++)
    {
        cout<<B[i]<<endl;
    }
}

さいごに

この高速ゼータ変換の$${10}$$進数版がARC136-Dに出たので書きました。