pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

高速メビウス変換

yukicoder 546: オンリー・ワン

https://yukicoder.me/problems/no/546 解法 高速メビウス変換というものを紹介する。高速メビウス変換というのは以下のような処理である。 for (int i = 0; i < n; i++) { for (int j = 0; j < 1 << n; j++) { if (~j >> i & 1) { a[j | 1 << i] -= a[j]; }…

ゼータ変換とメビウス変換

ゼータ変換$\zeta$とメビウス変換$\mu$はどちらも関数 $f:2^n \to R \quad(R: ring)$ に対する変換である。