はてなブックマーク

要約 本記事では、競技プログラミングに頻出のゼータ変換・メビウス変換についてまとめました。 記事中のコードはpythonで記述されています。 1次元のゼータ変換 定義 $f[0], \dots, f[N-1]$が与えられている。 このとき、$\displaystyle g[x] = \sum_{i \le x}f[i]$となる$g$を、$f$のゼータ変換という。 また、逆に$f$を$g$のメビウス変換という。 アルゴリズム 上の定義を落ち着いて読むと、$f$のゼータ変換$g$は$f$の累積和そのものだとわかります。 図で見ると上図のようになります。 累積和を知らない方はdrkenさんの記事を見てください。 念のため累積和の計算を復習しよう。 配列$f$が与えられているとき、$f$のゼータ変換はlist(itertools.accumulate(f))となる。 もしくは、in place に

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 概要 この記事は数値計算 Advent Calendar 2018の4日目の記事です。 本記事では準モンテカルロ法(Quasi-Monte Carlo, QMC)というアルゴリズムを紹介します。 準モンテカルロ法は、高次元の超立方体$[0,1]^s$上の関数を数値的に積分するためのアルゴリズムです。 積分ノードを「超一様性」を重視して選ぶことで、次元の呪いの回避とモンテカルロ法よりも高速な収束を目指します。 追記：この記事を発展させた日本語のサーベイ論文が出版されました。 次元の呪い $[0,1]^s$上の関数を数値積分しようと思ったと