subset_convolution

関数 · 部分集合畳み込み $c[S]=\sum_{T\subseteq S}a[T]b[S\setminus T]$ を求める

template <class T>
std::vector<T> subset_convolution(const std::vector<T> &a, const std::vector<T> &b);

概要

部分集合畳み込み $c[S]=\sum_{T\subseteq S}a[T]b[S\setminus T]$ を求める

パラメータ

戻り値

部分集合畳み込み。入力長を含む最小の2の冪まで0で補われる

計算量

• 出力長を $N=2^n$ として $O(n^2N)$