乐胖代购免代理版

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
- ある2つの配列を1つに纏める　参考1 参考2
- AtCoder LibraryにNTT実装があるここ
- FFT : Fast Fourier Transform, 高速フーリエ変換
  - C[k] = sum{i=0...k}A[i]*B[k-i]を高速化する(O(NlogN))
  - 流れ「1. 配列A,Bを高速フーリエ変換する」「2. 配列CをC[i] = A[i] * B[i]で作る」「3. 配列Cを逆高速フーリエ変換すると答え」
  - 二次元FFTというのもある
  - 組合せ問題を解くのにFFTを使ったりする多項式を使って組合せを求める例
  - 神「ビットマスクの掛け合わせを行う問題はFFTかも」
  - FFTでもしTLEしてしまう場合はdouble計算をfloatにするテクがある(1.5倍くらい早くなるが、誤差ミスが起こる可能性があるこの問題では誤差WAした)
  - FFTでは総じてTLEが厳しいので、注意して実装しよう
  - C[k] = sum{k=i*j}A[i]*B[j]っぽいことが高速にできる
    - この問題 kirikaさんのテキストの31ページに言及がある
    - 概要としてはFFTする前に配列の順番を入れ替えてFFTして上手く戻すことでできる。原始根と累乗を使えば積が和になってうまいことやれる
    - 添字のこういうテクは一般的なテクになりうるか？
    - AGC047 Product Modulo
  - Online FFT
    - 何がオンラインなのか分からん
    - CF309 Kyoya and Train 解説
    - CC Chef Counts Semi-BSTs 解説
  - 複数配列を全部FFT/NTTするときのマージテク
    - 「畳み込みしたい配列群の中からサイズが小さいものを2つ取ってきて、畳み込み計算をする」というのを配列が1つになるまで繰り返していけば、配列の要素数の総和をNとすると、O(Nlog^2N)で計算可能
- アダマール変換
  - C[i] = sum{j xor k} A[j]*B[k]を高速化する(O(NlogN))
  - 参考1 参考2
kazumaさんのgcd畳み込み（すごい）
- yukicoder No.886 Direct (gcd畳み込み)
👊パンチ👊ゼータ変換👊パンチ👊