ABC 452 E — You WILL Like Sigma Problem

考察

要求はi=1,…,N、j=1,…,Mの全組のA_iB_j(i mod j)。i<jも含まれ、その場合i mod j=iである。固定jで商k=floor(i/j)が一定なら、剰余はi−jkという一次式になる。

PA[t]=Σ_{i=1}^t A_i、PIA[t]=Σ_{i=1}^t iA_i、PA[0]=PIA[0]=0を用意する。各j=1,…,Mについて、まず商0の区間[1,min(N,j−1)]からB_j·PIA[min(N,j−1)]を足す。次にk=1,…,floor(N/j)についてl=jk、r=min(N,j(k+1)−1)とし、

B_j·((PIA[r]−PIA[l−1])−jk(PA[r]−PA[l−1]))

を足す。全演算をmod 998244353で行う。j>Nなら商0の項だけであり、N≠Mでも同じ手順で全組を覆う。

例えばN=1,M=2,A=(1),B=(1,1)ではj=1の寄与0、j=2の商0の寄与1なので答え1。商1以上だけを走査するとこの最小反例を落とす。

全pair列挙はO(NM)だが、商0は各jで定数時間、残りのblock数はΣ_{j≤min(M,N)}floor(N/j)=O(N log N)。剰余を商一定区間へ分け、二つの重み付きprefix和から区間総和を計算すればO(N log N+M)になる。

典型の発動条件

商一定区間の分割

発動条件: floor(i/j) や i mod j を全 pair で総和したいとき。

固定 divisor ごとに quotient が一定の連続区間を走査する。

重み付き prefix sum

発動条件: 区間内で係数が index の一次式になる総和を求めたいとき。

ΣA_i と ΣiA_i を組み合わせる。

問題固有の要素

mod を不規則な値として扱わず、quotient ごとの一次式へほどくと区間集約できる。

別の問題へ持ち帰る視点: 二重 loop でも内側長が N/j なら、総計を調和級数で評価して採用可能性を判断する。

正当性

各jの商0区間は[1,min(N,j−1)]、正の商kの区間は[jk,min(N,j(k+1)−1)]で、互いに素かつi=1,…,Nを覆う。商0ではi mod j=i、それ以外ではi−jkなので、提示したprefix差が各区間の重み付き剰余和を与える。全j=1,…,Mの寄与を足せば要求する全ordered pairを一度ずつ数える。

実装上の注意

  • NはAの長さ、MはBの長さ。jをMまで走査し、j>Nでは商0だけを加える。
  • PA[0]=PIA[0]=0、商0の右端min(N,j−1)を使う。商1以上のbucketへ重ねない。
  • 各積は64 bitで中間計算し、prefix差と最終値をmod 998244353で正規化する。

復習の核

  • 一つの j で quotient block を列挙し、i mod j=i-jk の区間寄与式と全 block 数の調和級数評価を手で導く。

計算量と制約

時間

O(N log N+M)。二つのweighted prefix和で各商bucketを定数時間評価する。

空間

O(N+M)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

You WILL Like Sigma Problem の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 整数境界と同値区間を正確に分ける

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

    主タグ: 整数境界・同値区間分割

    補助タグ: 累積和・差分配列

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

    学習の位置

    体系上の位置: 整数境界と同値区間を正確に分ける

    • floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。

    先に読む単元:

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

    • 素因数指数による整数条件の分解。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題