考察
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.
出典