noshi91のメモ

データ構造のある風景

2023-03-01から1ヶ月間の記事一覧

メモ: Bostan-Mori 法で計算できるものまとめ

\begin{align} \frac{P(x)}{Q(x)} &= \frac{P(x) Q(-x)}{Q(x) Q(-x)} \cr &= \frac{E(x ^ 2) + x O(x ^ 2)}{V(x ^ 2)} \end{align} であるから、 \begin{align} \left \lbrack x ^ k \right \rbrack \frac{P(x)}{Q(x)} &= \begin{cases} \displaystyle \left…

JOI 2022/2023 春季トレーニング 警備員 (Security Guard)

解法の説明は公式解説に任せるとして、いくつかの事実についての証明を書きます。 公式解説を見れてないのでどこが証明されてどこが証明されてないか分からない (もしかすると方針自体違うかも)。 治安が低いほど が大きいのが混乱の元なので、治安という言…