hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 2種類の畳み込み subset convolution 資料1 資料2 資料3 ゼータ変換とメビウス変換は逆変換の関係にある ゼータ変換（状態xを含む状態yを全列挙） 高速ゼータ変換でO(n2^n) g[x] = sum{y⊆x}f(y) → rep(i, 0, N) rep(msk, 0, 1 g[x] = sum{x⊆y}f(y) → rep(i, 0, N) rep(j, 0, 1 参考 高速ゼータ変換は環で動く（+, *, max, gcdなど） メビウス変換（状態xの部分状態yを全列挙） 高速メビウス変換でO(n2^n) g[x] = sum{y⊆x}(-1)^|x-y| g[y] … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F05%2F20%2F125607" title="競技プログラミングにおける畳み込み問題まとめ（FFT,アダマール変換,メビウス変換,ゼータ変換） - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-05-20 12:56:07 rich https://blog.hamayanhamayan.com/entry/2017/05/20/125607 1.0 100%