monoid exponentiation・連結演算doubling

概要

長さ・値・補助剰余を含む要約の結合則と単位元を定義し、巨大な反復連結を二分累乗する。

考え方

結合的な演算と単位元があれば、同じ元をK回合成する値を二分累乗で求められる。整数積だけでなく行列・写像・文字列の要約にも同じ原理を使える。

単位元e、演算⊗、基準元aに対しres=e,power=a,k=Kで始める。kの下位bitが1ならres←res⊗power、次にpower←power⊗power、k←floor(k/2)とし、k=0でresを返す。不変式 res⊗power^k=a^K を保つ。奇数時は一個をresへ移し、残りの偶数個を二個ずつまとめたので、結合則だけで成立する。K=0の空反復はeである。

十進文字列の連結なら要約(v,p)を「値v」と「10^長さの剰余p」とし、(v,p)⊗(w,q)=(vq+w,pq)、空列e=(0,1)とする。三つを結合した値はどちらの括り方でもvqr+w r+zになり結合的である。基準文字列の要約を累乗すれば、そのK回連結を実際に展開せず評価できる。

成立条件と計算量

O(log K)回の合成に、一回の演算費用を掛ける。可換性や逆元は不要で、K=0は単位元。負の指数には可逆性が必要。値の表現が途中で大きくなる場合は合成を定数時間と数えない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。結合則と単位元を定義し、数値以外の反復合成にも二分累乗を使う。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-monoid-exponentiation

monoid exponentiation・連結演算doubling

習得する技能

  • 反復対象を閉じた結合的要約へ持ち上げ、monoidの二分累乗で巨大な連結・合成を評価できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

長さ・値・補助剰余を含む要約の結合則と単位元を定義し、巨大な反復連結を二分累乗する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • monoid exponentiation・連結演算doublingの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠