ABC 384 F — Double Sum 2

考察

各和sをv2(s)=kで層分けすると目的値はs/2^k。d_kを2^kで割り切れるi≤jの和の総和とすれば層はd_k−d_{k+1}になる。各kについてj昇順に、現在A_jをその剰余counterへ先に登録し、補数剰余のcount C,sum SからC A_j+Sを加える。これでi≤jの対角も含み各pairを一度数える。登録を後にするとi<jだけなので、別途対角の奇数部分を足す必要がある。

典型の発動条件

倍数条件の累積量から隣接差を取ってexact p進指数へ戻す。補数剰余をcountとsumで集約し、pairの添字条件に登録時点を合わせる。

問題固有の要素

対象はi≤jなので対角pair(A_j,A_j)も寄与する。対角の和2A_jの奇数部分はA_jの奇数部分に等しい。

正当性

d_kを2^kで割り切れるi≤jの和A_i+A_jの総和とすると、v2がexactly kの層はd_k−d_{k+1}。各層を2^kで割ると目的の奇数部分になる。j走査で自身を先に登録してから補数剰余を照会すればi≤jが全て一度集計される。これを全kで差分すれば各pairが唯一の層で数えられる。

実装上の注意

先にA_jを登録してから補数剰余をlookupする。lookup後登録の実装なら全jの対角寄与を別加算する。各d_kと答えは64bit、負剰余は正規化し、最大和を超えた層は0とする。

復習の核

A=(1,3)ではi≤jの三和2,4,6から答え5。i<jだけの1と混同しない。余りが自分自身の補数になるcaseの登録順を確認する。

計算量と制約

時間

O(N log V)期待時間、V=2max A。各2冪の剰余をhash集計する。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1\le N\le 2\times 10^5; 1\le A_i\le 10^7; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 素因数分解と約数構造

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 素因数・約数分解

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

      学習の位置

      体系上の位置: 素因数分解と約数構造

      • 整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。

      この解説で扱わないこと:

      • 床関数や整数根の値が一定となる区間への分割。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題