NISHIO Hirokazu
[Translate]
メビウス変換
多義語なので要注意。
Möbius transformation - Wikipedia
幾何学における平面上のメビウス変換:
メビウス変換 - Wikipedia
Möbius Transform
Möbius inversion formula - Wikipedia
(Möbius Transformからリダイレクトされる)
メビウスの反転公式 - Wikipedia
Möbius function - Wikipedia
メビウス関数 - Wikipedia
>
メビウス関数は、数論や組合せ論における重要な関数である
競技プログラミング界隈で、特に包除原理などと関連して「メビウス変換」と呼ばれてる概念は前者とは関係ない。
競技プログラミング界隈での「メビウス変換」という用語の指す意味に揺れがあるという指摘
高速ゼータ変換/高速メビウス変換 - naoya_t@hatenablog
競技プログラミング界隈でたまに言及されるFast Subset Convolutionの論文
Fourier Meets Mobius: Fast Subset Convolution
この論文では古典的なメビウス変換として下記の解説をしている
この概念を指すもっと誤解の余地のない言葉として「
Sum over Subsets
(SOS)」がある
使用例:
SOS Dynamic Programming Tutorial - Codeforces
関連
高速メビウス変換
Tweet
Related Pages
包除原理
Sum over Subsets
ゼータ変換/メビウス変換20201105
高速メビウス変換
畳み込み入門
インドラの真珠
→
古典的メビウス関数
×
整除関係
×
半順序
×
隣接代数
×
ゼータ関数
×
べき集合
×
包除原理
×
差分作用素
×
Sum over Subsets
×
高速ゼータ変換
→
メビウス関数
→
高速ゼータ変換
×
高速メビウス変換
×
畳み込み
×
部分集合列挙
→
ビット演算
"
Engineer's way of creating knowledge
" the English version of my book is now available on
[Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from
[Scrapbox]
at
11/23/2025, 5:39:46 PM
[Edit]