考察
2^i 未満で popcount=j の数の個数 f(i,j) と総和 s(i,j) を持てば、下位 i bit を自由に選ぶブロックの寄与を O(1) で求められる。N の 1 bit を上位から一つずつ 0 に変えた最初の位置で [0,N) を互いに素なブロックへ分割でき、残りの必要な 1 の個数だけが各ブロックを決める。f(i,j)=f(i-1,j)+f(i-1,j-1)、s(i,j)=s(i-1,j)+s(i-1,j-1)+2^{i-1}f(i-1,j-1) で個数と値の総和を同時に遷移できる。現在の N の 1 bit を 0 にしたブロックでは、既に確定した上位 prefix は全候補へ共通なので、その寄与は prefix×f(i,必要 popcount) となる。
採用する候補: 個数と総和を前計算した bit digit DP で、N の立っている bit を上位から走査する
各ブロックの下位 bit 寄与 s と確定済み上位値×個数 f を加え、最後に popcount(N)=K なら N 自身を加える。各 testcase O(log N)。
棄却する候補: 1 から N まで popcount を計算して条件を満たす値を足す
N は 2^60 未満まであり、T=100 なので数値を直接列挙できない。
i,j≤60 の f,s を mod 998244353 で前計算する。N の set bit d を降順に見て、それ以前に確定した 1 の数を used、値を prefix とし、s(d,K-used)+prefix·f(d,K-used) を有効範囲なら加算する。最後に popcount(N)=K なら N を足す。
典型の発動条件
bit digit DP
発動条件: 上限 N 以下で bit 個数など prefix 依存の条件を数えたり総和したりするとき。
N と初めて異なる 1 bit の位置ごとに下位自由ブロックを列挙する。
個数と総和の同時 DP
発動条件: 候補数だけでなく候補値の総和が必要なとき。
下位 bit の個数 f と総和 s を組にし、新たに立てる最高 bit の寄与を個数倍で加える。
問題固有の要素
候補値の総和を一つずつ生成せず、「共通 prefix の個数倍」と「自由 suffix の総和」へ分解する。
別の問題へ持ち帰る視点: digit DP で値の総和を求めるときは、状態ごとに通り数と数値和を対で持ち、固定桁の値を通り数倍して足す。
正当性
N未満の整数は、上から見てNと初めて異なる1bitを0にする位置で一意分類される。その上位prefixは固定され、下位 d bitに必要個数の1を選ぶ。各 block の総和は lowerSum+prefix×countで、互いに素な block の加算は全[0,N)を一度ずつ覆う。popcount(N)=Kの場合のみN自身を追加して[0,N]を得る。
実装上の注意
- 必要個数 K-used が負または d を超えるブロックは 0 とする。N 自身の加算を忘れず、2^i と総和は各演算で mod を取る。
復習の核
- N=1、K=1、Kがbit長より大きい場合、N=2^m-1、N自身だけが条件を満たす場合を小さい全列挙と比較する。
計算量と制約
時間
bit数 B=60、T case。個数・総和前計算 O(B²)、各上限の bit走査 O(B)、全体 O(B²+TB)。
空間
前計算二表 O(B²)、case を逐次処理すれば追加 O(B)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 100; 1 \leq N < 2^{60}; 1 \leq K \leq 60; T, N, and K are integers.
出典