noshi91のメモ

データ構造のある風景

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

文字列の連結と辞書順の関係を冪級数で証明

概要 cp-unspoiler この問題の公式解説にある補題群を冪級数を用いて証明する。 定義 この記事内では以下のように定義する。 また、列の大小関係を辞書順で定める。 辞書順関連 を十分小さい正の実数とし、 を で定める。 このとき について となる。 定理 :…

FPS の合成と逆関数、冪乗の係数列挙 Θ(n (log(n))^2)

概要 温めておいたのですが、ABC で似た問題が出題されてしまったので (想定解は違いましたが) 起源が問題になる前に公開しようと思います。 問題 標数の十分大きい体 上の形式的冪級数 の 次までの項が与えられる。 を求めよ。 ただし、 を係数とする次数 …