ABC 317 F — Nim

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Nim の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 上限制約付き桁DP

主題
  • 上限制約付き桁DP: 数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 上限制約付き桁DP

    補助タグ: 集合上の包除原理

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

    学習の位置

    体系上の位置: 上限制約付き桁DP

    • 数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題