ABC 283 Ex — Popcount Sum

考察

popcount総和はbitごとの1の個数の和なので、k=0…29について合同条件を満たしbit kが1の整数数を数えればよい。

合同条件の整数はA_t=R+tMという等差数列になり、bit indicatorをfloorの差へ変えればfloor_sumを適用できる。

採用する候補: 各bitで1_{bit k(A)=1}=floor((A+2^k)/2^{k+1})−floor(A/2^{k+1})を使い、合同等差数列上の二つのfloor和をACL floor_sumで求める。

Nまでの対象整数を列挙せず、各bitをlogarithmicなEuclid型計算へ集約でき、T≤10^5に対応する。

棄却する候補: R mod Mの整数を1からNまで列挙し、各popcountを足す。

M=1,N=10^9のtestが多数あると対象数が巨大になる。

bit kはA mod2^{k+1}が[2^k,2^{k+1})にあるindicatorで、floor差が周期blockを正確に数える。

t=t_0,…,t_0+n-1にshiftすると各項はfloor((M·i+b)/2^{k+1})となり、floor_sum(n,mod,M,b)の形になる。

最小正のA=R+tMと最大≤Nからt rangeを求める。各kでm=2^{k+1}とし、shift後b=R+t_0Mについてfloor_sum(n,m,M,b+2^k)−floor_sum(n,m,M,b)をanswerへ足す。

典型の発動条件

popcountのbit別寄与

発動条件: 多数整数のpopcount総和を求め、各bitの立つ個数を別々に数えられるとき。

sum_x popcount(x)=sum_k count(bit_k=1)へ交換する。

floor sum

発動条件: 等差数列上のfloor((ai+b)/m)の総和が必要なとき。

Euclid algorithm型floor_sumでindex数に依存せず計算する。

問題固有の要素

周期的bit patternを直接区間数えせず、半周期shiftしたfloor quotientの差にすると合同等差列とも自然に合成できる。

別の問題へ持ち帰る視点: periodic 0/1 indicatorはfloor((x+shift)/period)-floor(x/period)で表せないか試す。

正当性

対象値は正の等差数列R+tMに一意に並ぶ。bit kの指示値はfloor((A+2^k)/2^{k+1})−floor(A/2^{k+1})であり各Aについて0または1になる。これを等差数列で合計した二つのfloor_sumの差は当該bitの1個数そのもの。全bitを足すことでpopcount総和を得る。

実装上の注意

  • R=0ではt=0のA=0を除き最初をMにし、1≤A≤Nの項数を正確に作る。
  • floor_sum内部積とanswerは64 bitを使い、b=R+t_0Mが大きい場合も型幅を確保する。

復習の核

  • k=2のbit pattern00001111…とfloor((A+4)/8)-floor(A/8)をA=0…15で並べ、合同列へ抜き出して確認する。

計算量と制約

時間

各case O(log N·log max(N,M))。30bitそれぞれをEuclid型floor_sumで数える。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 10^5; 1 \leq M \leq N \leq 10^9; 0 \leq R < M; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Popcount Sum の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 格子点転置によるfloor_sum

主題
  • 格子点転置によるfloor_sum: Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 格子点転置によるfloor_sum

    補助タグ: 寄与の数え上げと順序交換

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 格子点転置によるfloor_sum

    • Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。

    先に読む単元:

    • 局所寄与へ分解して集計順を交換する — 数える対象を一意に固定し、その対象を含む選択や組の個数へ集計順を交換する。要素・組・区間・値のどれを固定すると重複が消えるかを比較する。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題