はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける高速ゼータ変換・高速メビウス変換問題まとめ

高速ゼータ変換・高速メビウス変換

  • 互いに逆関数の関係にある
  • 資料1 資料2 資料3
  • 高速メビウス変換はその形から包除原理で良く用いられる
  • 高速ゼータ変換
    • g[x] = sum{x⊆y}f(y)
    • rep(i, 0, N) rep(j, 0, 1 << N) if (!(j & (1 << i))) f[j] += f[j | (1 << i)];
  • 高速メビウス変換
    • g[x] = sum{y⊆x}(-1)^|x-y| g[y]
    • rep(i, 0, N) rep(j, 0, 1 << N) if (j & (1 << i)) f[j] -= f[j ^ (1 << i)];

問題

高速メビウス変換による包除原理の高速化

高速ゼータ変換

どっちも使う

どっちだろう