高速ゼータ変換を知っていますか?
はじめに
高速ゼータ変換、名前いかついですよね。
実は次元の高い累積和みたいなことをやっているだけです。
高速ゼータ変換とは
$${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に出たので書きました。
この記事が気に入ったらサポートをしてみませんか?