集合べき級数解説 集合べき級数関連 (4) 問題例
Distinct Multiples (ABC 236 Ex)
ユーザー解説に書いた通り．集合べき級数の $\exp$ で $O(N^22^N)$ 時間で解ける．
Connectivity 2 (ABC 2...
maspy
集合べき級数解説 集合べき級数解説 集合べき級数関連 (3) 集合べき級数の Power Projection
参考文献
Elegia さん：
転置原理により本記事で扱う問題の解法が導出できることについて述べている．
ryuhe1 さん：
転置原理について詳細な記述がある．
noshi91 さん：
...
集合べき級数解説 集合べき級数 (2) 多項式との合成
参考文献
Elegia さん：
本記事で扱っているアルゴリズムはここで紹介されているものとほぼ同一です．ただし以下の点について，定式化や議論を変更・追加しています．
分母 $\frac{1}{k!}$ について説明し，...
集合べき級数解説 集合べき級数 (1) subset convolution
参考文献
(arXiv) Fourier meets Mobius : Fast subset convolutionFourier Meets Mobius: Fast Subset Convolution
Elegi...
アルゴリズム・数学 モノイド作用に関する離散対数問題
概要
本記事では、次の離散対数問題の変種を扱います。
$X$ をモノイド、$S$ を集合とし、$X$ が $S$ に左作用しているとする。$x\in X$ および $s, t \in S$ および、正整数 $N$ が与えられる...
アルゴリズム・数学 分割統治による静的列の区間積クエリ
概要
本記事では、次の形の問題を扱います。
$X$ をモノイドとして、$(x_0, \ldots, x_{N-1})$ を $X$ の元の列とする。次の形の $Q$ 個のクエリに答えよ：区間 $[a,b)$ が与えられるので、...
Library Checker [Library Checker] Min of Mod of Linear
概要
問題文 → ■自分の提出 → ■
$O(\log M)$ 時間で解く方法を解説します。
準備：最良近似分数と Farey 数列
この記事において、「有理数 $\frac{p}{q}$」などと書けば、$p,q$ は互...
問題解説 [yukicoder] No.2166 Paint and Fill
概要
問題文 → ■公式解説 → ■自分の提出 → ■
制約 1 の取り扱いが、少し別解っぽかったので書いておきます。
公式解説補足
$f=1$ となる（疎な）多項式と定数 $N$ に対して、$F_k = f(x)^N$ で定...
問題解説 [yukicoder] No.2114 01 Matching
概要
問題文 → ■公式解説 → ■自分の提出 → ■
解法
$K=1$ に帰着します。次のような問題が解ければよいです。
点 $X_0, \ldots, X_N$ （$X_i \leq X_{i+1}$）がある。各点は...
アルゴリズム・数学 slope trick (3) slope trick の凸共役
slope trick (1) 解説編
slope trick (2) 問題編
概要
凸関数の凸共役（Legendre-Fenchel 変換）とその性質について、軽くまとめます。さらに、slope trick による...