考察
Nは10^18まであるので倍数を列挙できない。一方、A_i≤10 なら三つの剰余の直積は小さい。xor条件も各bitで独立なので、三数のbitを同時に決める桁DPを考える。
下位桁からなら、bit bにuを追加した剰余は (r+u·2^b) mod A_i で更新できる。上限比較flag f_iは、b桁処理後の X_i mod 2^b ≤ N mod 2^b の真偽と定義する。新しい上位bit uがNのbitより小さければtrue、大きければfalse、等しければ旧flagを引き継ぐ。上位桁の差が下位桁の大小を上書きするのが、MSB-firstのtightとの違いである。例えばX=1,N=2は下位1桁で超過しても、次の桁で上限以下になる。
初期状態は三つの剰余0・全flag trueの個数1。各bitではxorが0となる 000,011,101,110 の四通りだけを試す。60bit処理後の全flag true・全剰余0の値をZとすれば、0を許した三つ組の個数になる。
正整数へ戻すには零を含む組を除く。一つだけ0なら残り二数は等しい正の共通倍数なので、その個数は floor(N/lcm(A_j,A_k))。0の位置が違う三集合は互いに素で、全0はどれにも含まれない。全0一個を別に引き、答えは Z−1−Σ_{j<k} floor(N/lcm(A_j,A_k)) となる。
典型の発動条件
LSB-first digit DP
発動条件: bitwise 条件は各桁局所だが、剰余を下位桁から加算する方が自然なとき。
下位 prefix と上限下位 prefix の比較 flag を持ち、上位 bit 追加で更新する。
複数整数の同期 bit DP
発動条件: 複数数の xor/and 等が桁ごとに条件を課すとき。
同じ桁の bit tuple をまとめて列挙し、各数固有の剰余・上限状態を直積する。
問題固有の要素
A_i≤10 という制約は値列挙ではなく、三つの剰余状態の直積 ∏A_i を小さくするためにある。
別の問題へ持ち帰る視点: digit DP の状態数は桁数だけでなく、付随する modulus の積を見て方向を選ぶ。
正当性
上位bitが異なるときはその大小が全体の比較を決め、同じときだけ下位比較が残るので、flag更新は定義を保つ。各三つ組のbit列は一意であり、xor条件を満たす四通りの遷移が全候補を漏れなく数える。終端の比較と剰余で必要条件を絞り、一つだけ0の三集合と全0をそれぞれ除けば、正整数の三つ組だけが残る。
実装上の注意
- 0≤x≤N を数えた後の正数補正を忘れない。LSB comparison flag の遷移は全小例を列挙して検証し、60 bit で N の最高bitを覆う。
復習の核
- MSB-first の tight を惰性で使わず、剰余更新と xor に自然な LSB-first を検討する。下位比較 flag の意味を式で固定してから遷移を書く。
計算量と制約
時間
O(BA1A2A3)、B=60、各bit tripleは四通り、比較flagは八通り。
空間
O(A1A2A3)、bit方向rolling。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^{18}; 1 \leq A_i \leq 10; All input values are integers.
出典