格子点転置によるfloor_sum
概要
一次式の床和を格子点数とみなし、整数部分の取り出しと領域の転置でEuclid互除法型に再帰する。商一定区間の列挙とは異なり、傾きと法の交換が計算量を決める。
標準の床和F(n,m,a,b)=Σ_{i=0}^{n−1}floor((ai+b)/m)を、格子点数を保つ引数変換から導く。ABC443 Gは標準式の利用、ABC283 Exはbitごとの指示値への分解、ABC402 Gは床和の一般化を練習する問題である。以下では同じFを再利用する式を比較する。
定義: n≥0,m>0。a=qm+a′,b=rm+b′(0≤a′,b′<m)と分け、F=q·n(n−1)/2+rn+F(n,m,a′,b′)。負の係数でもfloor除算で非負剰余を取れば同じ式。
転置: 正規化後a>0としてy=floor((an+b)/m),c=(an+b) mod m。Fは0≤i<nかつ1≤j、mj≤ai+bの格子点数。iをn−1−iに反転し、jをy−tと書くと各t=0,…,y−1で許されるiの数はfloor((mt+c)/a)。従ってF(n,m,a,b)=F(y,a,m,c)。
終了と計算量: a=0なら正規化後の和は0。y=0でも0。転置後の法はa<mとなり、次の係数正規化でm mod aが現れる。Euclid互除法と同じ引数減少なので反復はO(log m)。
ABC283 Exでは対象列v=b+Miのbit kの指示値がfloor((v+2^k)/2^{k+1})−floor(v/2^{k+1})。この二つのFを計算し、bitごとの寄与を足す。
考え方
Σ_{0≤i<n} floor((ai+b)/m)を、aとbの商の寄与と剰余へ分ける。残る格子点領域の軸を交換するとEuclid型に引数が小さくなり、全iを走査せず和を求められる。
再帰式を反復へ落とす
累積ans=0から始める。n=0ならansを返す。各段でa=qm+a′、b=rm+b′をfloor除算で作り、ansへq·n(n−1)/2+rnを足し、a,bをa′,b′へ置き換える。これで「元の床和=ans+現在のF」という不変量を保つ。
a=0なら残り0で終了する。それ以外はz=an+bを旧引数で一度計算し、y=floor(z/m)、c=z mod mを得る。y=0なら終了、そうでなければ(n,m,a,b)を同時に(y,a,m,c)へ置き換える。格子点転置の等式が残りのFを保存し、次段の正規化でEuclidの余りが現れる。逐次代入で旧mや旧aを失わない。負のa,bでも最初のfloor正規化以降の剰余は非負になる。
成立条件と計算量
m>0、非負の標準形ではO(log m)段。負のa,bはfloor除算で正規化して寄与を分離する。三角数やa·nのoverflowを扱う。定義の半開区間を変えると端の一項が変わる。
問題一覧
- ABC443 G「Another Mod of Linear Problem」 公式問題
技能・出典
主題: 格子点転置によるfloor_sum(Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。)。主タグ: 格子点転置によるfloor_sum
- ABC283 Ex「Popcount Sum」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: 格子点転置によるfloor_sum(Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 格子点転置によるfloor_sum / 補助タグ: 寄与の数え上げと順序交換
- ABC402 G「Sum of Prod of Mod of Linear」 公式問題
技能・出典
主題: 格子点転置によるfloor_sum(Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。)。主タグ: 格子点転置によるfloor_sum
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC313 G「Redistribution of Piles」 公式問題主題: 同値な状態を正規化する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 格子点転置によるfloor_sum(Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。)。主タグ: 状態・配置の正規化 / 補助タグ: 格子点転置によるfloor_sum
- ABC372 G「Ax + By < C」 公式問題
技能・出典
主題: Convex Hull Trick・直線包絡(一次関数候補の傾き・交点順を保ち、query点で包絡線上の最適な直線を選べる。)。既習技能: 格子点転置によるfloor_sum(Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。)。主タグ: Convex Hull Trick・直線包絡 / 補助タグ: 格子点転置によるfloor_sum
前提・学習成果・出典
習得対象の目安: 黄色(2000–2399)。床和を格子点数へ写し、傾きと法の交換からEuclid型の再帰を導く。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-euclidean-floor-sum
格子点転置によるfloor_sum
習得する技能
- Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
一次式の床和を格子点数とみなし、整数部分の取り出しと領域の転置でEuclid互除法型に再帰する。商一定区間の列挙とは異なり、傾きと法の交換が計算量を決める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- 格子点転置によるfloor_sumの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。