エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
高速ゼータ変換、高速メビウス変換 - omochan's diary
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
高速ゼータ変換、高速メビウス変換 - omochan's diary
包除原理で活躍する二つのアルゴリズムです。この2つの記事がわかりやすかったです。 高速メビウス変換... 包除原理で活躍する二つのアルゴリズムです。この2つの記事がわかりやすかったです。 高速メビウス変換について - 篠突く雨の日記 ゼータ変換とメビウス変換 - pekempeyのブログ メビウス:∩→∪ ゼータ :∪→∩と覚えればいいです。たぶんメビウスの方がよく使うと思います。なぜなら包除原理は∩を∪に変換する公式と考えられるからです。 例えば2,3,7のうちどれかの倍数(集合でいうと∪の関係)である数が100までの自然数で何個あるか考えましょう。 2かつ3の倍数(つまり集合でいうと∩の関係)である数の個数などは簡単に求まります。これをメビウス変換に渡せば求めるべき値が得られます。 ゼータ変換はこの逆で∪で表される関係を∩にしてくれます。 アルゴリズムはbitdpで、dp[i][S]:(i-1番目までのbitは包含関係が満たされればなんでもいいけどi番目からはSと等しい要素の和)でやります