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

hamayanhamayan's blog

競技プログラミングにおける畳み込み問題まとめ(FFT,アダマール変換,メビウス変換,ゼータ変換)

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 << N) if (msk & (1 << i)) sm[msk] += sm[msk ^ (1 << i)];
      • 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)];
      • 参考 高速ゼータ変換は環で動く(+, *, max, gcdなど)
    • メビウス変換(状態xの部分状態yを全列挙)
      • 高速メビウス変換でO(n2^n)
      • 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)];
      • メビウス変換じゃないけど似てる)g[x] = max{y⊆x} g[y] → rep(i, 0, N) rep(j, 0, 1<<N) if(j & (1 << i)) chmax(f[j], f[j + (1 << i)])
  • normal comvolution
  • kazumaさんのgcd畳み込み(すごい)
  • 👊パンチ👊ゼータ変換👊パンチ👊

問題

https://twitter.com/uwitenpen/status/869609817794502656

【発展的話題】 NTT