Subset Convolution（部分集合畳み込み）

集合関数f, gの部分集合畳み込みを計算します。

一般形

let result =
  subsetConvolution(
    f,
    g,
  )

引数

• f: 1個目の集合関数
• g: 2個目の集合関数
• T: 要素型。加算・減算・乗算を利用できる必要があります

長さが2^kの配列では、添字maskをk要素集合の部分集合として 扱います。

前提条件

• f.len == g.len
• 入力長は正の2冪
• 空列は使用できない

条件を満たさない場合はValueErrorを送出します。

返り値

返り値は入力と同じ長さのseq[T]です。

各集合Sについて、

result[S] = sum f[T] * g[S xor T]

です。和はSの全部分集合Tについて取ります。

入力f, gは変更しません。

具体例

import atcoder/modint
import atcoder/extra/math/subset_convolution

type mint = modint998244353

let
  f = @[
    mint.init(1),
    mint.init(2),
    mint.init(3),
    mint.init(4),
  ]

  g = @[
    mint.init(5),
    mint.init(6),
    mint.init(7),
    mint.init(8),
  ]

  result =
    subsetConvolution(
      f,
      g,
    )

doAssert result == @[
  mint.init(5),
  mint.init(16),
  mint.init(22),
  mint.init(60),
]

添字0, 1, 2, 3は、それぞれ空集合、{0}、{1}、{0,1}を 表します。

関連API

• orConvolution: OR畳み込み
• andConvolution: AND畳み込み
• xorConvolution: XOR畳み込み
• zeta_transform: subset/superset zeta transformを直接扱う低水準API

部分集合を互いに素な2つの部分へ分ける畳み込みには subsetConvolutionを使います。

計算量

入力長を2^kとすると、

• 時間: O(k^2 * 2^k)
• メモリ: O(k * 2^k)

内部ではrank付きゼータ変換とメビウス変換を使用します。