ABC 339 F — Product Equality

考察

巨大な整数の積をそのまま求めず、複数の素数で割った余りを照合する。積が等しければ余りも必ず等しいため、異なる積を誤って一致とみなす確率だけを抑えればよい。余りの組ごとに入力の個数を数えておくと、三つ目の添字を全探索せずに答えへ加算できる。

まず、AiAj=AkA_iA_j=A_k を満たす添字の三重組をそのまま調べると N3N^3 通りになる。しかし、順序付き対 (i,j)(i,j) を固定すれば、必要なのは値 AiAjA_iA_j が入力に何個あるかである。値ごとの頻度表を使えば、調べる積は N2N^2 個に減る。それでも各整数は最大1000桁あり、すべての積を多倍長整数で計算して巨大な値を検索キーにするのは重い。

ここで、等しいかどうかを調べるために、積の全桁が必要かを考える。法を pp とすると、積の余りは両因子の余りから求められる。

(AiAj) mod p=((Ai mod p)(Aj mod p)) mod p(A_iA_j)\bmod p=((A_i\bmod p)(A_j\bmod p))\bmod p

一つの法では、例えば法7で 2×32\times3 と13がともに余り6となる。そこで独立に選んだ複数の素数を法にし、すべての余りが一致した場合だけ等しいとみなす。この余りの組を指紋(fingerprint)と呼ぶ。

候補集合 PP を区間 [109,2×109][10^9,2\times10^9] 内の全素数とし、その個数を K=∣P∣K=|P| とする。PP から独立一様に、重複を許して RR 回選んだ法を p1,…,pRp_1,\ldots,p_R とする。具体的な抽出方法と KK の根拠は後で示す。本解説では公式解説の目安に合わせて R=20R=20 を使い、正当性で必要な回数を評価する。

各入力値の指紋を

Hi=(Ai mod p1,…,Ai mod pR)H_i=(A_i\bmod p_1,\ldots,A_i\bmod p_R)

と定める。十進文字列を先頭から読み、各法について余り h=0h=0 から、次の桁 dd ごとに h←(10h+d) mod pth\leftarrow(10h+d)\bmod p_t と更新すれば、大きな整数へ変換せずに指紋を作れる。tt は 1,…,R1,\ldots,R を動く。

頻度表 ff は最初は空とし、各 HkH_k に対して f[Hk]f[H_k] を1増やす。次に答えを0で初期化し、すべての順序付き対 (i,j)(i,j) について

Gij=((Hi)1(Hj)1 mod p1,…,(Hi)R(Hj)R mod pR)G_{ij}=((H_i)_1(H_j)_1\bmod p_1,\ldots,(H_i)_R(H_j)_R\bmod p_R)

を作り、f[Gij]f[G_{ij}] を答えへ加える。表にないキーの頻度は0とする。ここで (Hi)t(H_i)_t は指紋の第 tt 成分である。同じ法の列を、入力の指紋とすべての積に共通して使う。

典型の発動条件

randomized modular fingerprint

巨大整数の等式を大量に検査し、和や積を剰余上で計算できるときに使う。異なる値が衝突する確率は、非零の整数差を割る候補素数の割合から評価する。固定した大きな法を使うだけでは、乱択による保証にはならない。

multiset frequency集計

三変数の条件を「二変数から作る値」と「残り一変数の値」の一致へ分けられるとき、後者を頻度表へまとめる。同じ値の添字が複数あれば、その個数を加えるので、集合ではなく頻度を保持する。

問題固有の要素

入力の桁数制限から、偽の等式の整数差の大きさを抑えられる。その差が持てる大素因数は少ないため、候補素数を広く取るほど誤判定しにくくなる。一方、頻度表で計算をまとめても、誤って加算し得る三重組の総数は減らない。処理する対の数と、確率を評価する対象の数を分けて数えることが本問の要点である。

正当性

入力は法を選ぶ前に固定されているとする。以下の確率は、その固定入力に対して法をランダムに選ぶときの評価である。

真の等式 AiAj=AkA_iA_j=A_k は、どの法でも合同式を満たすので必ず数えられる。各 (i,j)(i,j) で頻度表が加えるのは、Gij=HkG_{ij}=H_k を満たす添字 kk の個数である。従って、偽の等式が一つも衝突しなければ、各正しい三重組をちょうど1回ずつ数える。誤りが起きる場合も、答えを過大にする方向だけである。

一つの偽等式を通してしまう素数は何個あるか

AiAj≠AkA_iA_j\ne A_k となる三重組を一つ固定し、非零の整数差を D=AiAj−AkD=A_iA_j-A_k と置く。制約 1≤Ai<1010001\leq A_i<10^{1000} より 0<∣D∣<1020000<|D|<10^{2000}。法 pp で誤って一致する条件は、pp が DD を割ることである。

候補集合 PP のうち DD を割る「悪い素数」の集合を BDB_D、その個数を b=∣BD∣b=|B_D| とする。これらは相異なる素数なので、その積も ∣D∣|D| を割る。各素数が 10910^9 以上であることから

109b≤∏p∈BDp≤∣D∣<10200010^{9b}\leq\prod_{p\in B_D}p\leq|D|<10^{2000}

となり、9b<20009b<2000、すなわち b≤222b\leq222 を得る。∣D∣=1|D|=1 なら悪い素数は0個である。

候補数 KK は、区間篩で数えると 47 374 75347\,374\,753 個である。具体的には ⌊2×109⌋=44721\lfloor\sqrt{2\times10^9}\rfloor=44721 以下の素数を篩で列挙し、候補区間を小区間に分け、それらの素数の倍数を消して残数を合計すれば求まる。端点はいずれも合成数なので、端点の包含による差はない。以下では保守的に K>4×107K>4\times10^7 だけを使う。この個数の計数は保証を確認するためのもので、解法の実行時に全候補を列挙する必要はない。

抽出方法と反復回数を対応させる

独立な復元抽出では、各回で KK 個の素数から一様に選ぶ。一つの偽等式が全 RR 回で衝突する確率は

(bK)R≤(222K)R\left(\frac{b}{K}\right)^R\leq\left(\frac{222}{K}\right)^R

である。法の重複を許しても、抽出を独立に行っていればこの式が成り立つ。

相異なる法を使いたい場合は、毎回、未選択の素数から一様に選ぶ非復元抽出にする。1≤R≤K1\leq R\leq K とすると、選んだすべてが悪い素数になる確率は超幾何分布の比

(bR)(KR)=∏t=0R−1b−tK−t≤(bK)R≤(222K)R\frac{\binom{b}{R}}{\binom{K}{R}} =\prod_{t=0}^{R-1}\frac{b-t}{K-t} \leq\left(\frac{b}{K}\right)^R \leq\left(\frac{222}{K}\right)^R

で抑えられる。積の式は R≤bR\leq b の場合で、R>bR>b なら確率は0である。各因子が b/Kb/K 以下なので、独立性を仮定せずに同じ上界へつながる。

全体の誤りは三重組の数で評価する

偽等式の候補は高々 N3N^3 個ある。どこか一つでも衝突する確率は、事象の和の上界(union bound)により

Pr⁡(答えを誤る)≤N3(222K)R\Pr(\text{答えを誤る})\leq N^3\left(\frac{222}{K}\right)^R

となる。頻度表の検索回数は N2N^2 回だが、一回の検索で最大 NN 個の添字 kk をまとめて数えている。従って、検索回数だけを掛けた N2(222/K)RN^2(222/K)^R はこの議論からは導けない。全三重組で同じ法を共有するため、衝突事象同士は独立とは限らないが、union boundにはその独立性は不要である。

許容する全体誤りを 0<η<10<\eta<1 とすれば、N3(222/K)R≤ηN^3(222/K)^R\leq\eta となるよう、

R≥⌈log⁡(N3/η)log⁡(K/222)⌉R\geq\left\lceil\frac{\log(N^3/\eta)}{\log(K/222)}\right\rceil

と選べばよい。本問では N≤1000N\leq1000、222/K<5.6×10−6222/K<5.6\times10^{-6} なので、R=4R=4 でも全体誤りは 10−1210^{-12} 未満、採用した R=20R=20 なら 10−9610^{-96} 未満となる。これは、公式解説が省略した精密評価を、候補素数の一様抽出という仮定の下で補ったものである。

実装上の注意

  • 素数を一様に選ぶには、区間 [109,2×109][10^9,2\times10^9] の整数を毎回独立一様に生成し、素数でなければ棄却して引き直す。各整数の提案確率が等しいため、素数だったという条件の下でも各候補は等確率になる。非復元抽出にする場合だけ、選択済みの素数も棄却する。本解説の手順は復元抽出なので、重複除去は必須ではない。
  • 一様な整数生成には uniform_int_distribution などの範囲生成を使う。一様なビット列を単に区間長で割った余りにすると、区間長が元の出力数を割り切らない限り偏る。また「ランダムな整数の次の素数」を採ると、直前の素数との間隔が広い候補ほど選ばれやすくなる。上の保証は理想的な独立一様乱数のモデルに対するもので、実装で使う疑似乱数生成器とは区別する。固定した法の列に対する任意入力の無誤りを保証するものではない。
  • 素数性は、44721以下の素数を前計算し、候補の平方根以下の素数による試し割りで確定できる。公式解説の添付コードは素数判定を省いて大きな整数を法にしているが、本解説の「悪い素数は高々222個」という保証をそのまま適用することはできない。
  • 辞書のキーには余りの組の全成分を含める。ハッシュ表の内部でハッシュ値が衝突しても、キー全体の等値比較で区別する。内部ハッシュ値だけをキーにすると、ここで証明していない別の誤りが加わる。
  • 余り同士の積は pt2≤4×1018<263−1p_t^2\leq4\times10^{18}<2^{63}-1、十進変換中の 10h+d10h+d は 2×10102\times10^{10} 未満なので、符号付き64 bit整数に収まる。ただし32 bit同士で先に乗算しないよう、乗算前から64 bit型にする。答えは最大 N3≤109N^3\leq10^9 だが、64 bitで集計してよい。
  • (i,j)(i,j) と (j,i)(j,i) は別の順序付き対として走査し、i=ji=j や i=ki=k も許す。入力値1も特別扱いしない。同じ値の重複を消さず、頻度表には出現数を残す。例えば入力が (1,1,2)(1,1,2) なら、1同士の積の寄与は 2×2×2=82\times2\times2=8、1と2の積の寄与は両順序で計4なので、答えは12となる。

復習の核

  • 巨大整数の等式を余りへ写すと、真の等式は必ず残る。偽等式の整数差を割る候補素数の個数と、候補集合の大きさから衝突確率を求める。
  • 計算を頻度表でまとめても、誤り得る等式の数は別に数える。本問は N2N^2 回の検索と N3N^3 個の三重組を区別する。
  • 複数の法を使うときは、法の本数だけでなく抽出分布を確認する。独立な復元抽出と一様な非復元抽出は、異なる確率式から同じ保守的上界につながる。

計算量と制約

時間

入力の総桁数を LL、素数生成・素数性判定の総時間を TgenT_{\mathrm{gen}} とする。剰余の構築は O(RL)O(RL)。平衡二分探索木の辞書では、長さ RR のキーの比較に最悪 O(R)O(R)、一検索に O(Rlog⁡(N+1))O(R\log(N+1)) かかる。頻度表の構築と全 N2N^2 対のキー生成・検索を合わせ、全体は

O(Tgen+RL+RN2log⁡(N+1))O\bigl(T_{\mathrm{gen}}+RL+RN^2\log(N+1)\bigr)

となる。ハッシュ表では、キーのハッシュ計算・等値比較の O(R)O(R) を含めて期待 O(Tgen+RL+RN2)O(T_{\mathrm{gen}}+RL+RN^2)。辞書内部の衝突が偏る最悪の場合は一検索で O(N)O(N) 個のキーを調べ得るので、ハッシュ表の全体最悪時間を同じ式にはできない。

素数生成も無料ではない。M=2×109M=2\times10^9、W=109+1W=10^9+1 をそれぞれ候補区間の上端と整数の個数とする。⌊M⌋\lfloor\sqrt M\rfloor 以下の素数の前計算は O(Mlog⁡log⁡M)O(\sqrt M\log\log M)。その個数を ss とすれば、一候補の試し割りは最悪 O(s)O(s) である。復元抽出で RR 個を得るまでの提案回数の期待値は RW/KRW/K なので、生成時間の期待値は

E[Tgen]=O(Mlog⁡log⁡M+(RW/K)s)\mathbb E[T_{\mathrm{gen}}] =O\bigl(\sqrt M\log\log M+(RW/K)s\bigr)

である。非復元抽出では提案回数の期待値を ∑t=0R−1W/(K−t)\sum_{t=0}^{R-1}W/(K-t) に置き換える。棄却を繰り返す生成法には有限の最悪試行回数はないため、辞書を木にしても生成を含む全体が決定的な最悪時間保証になるわけではない。

空間

入力文字列をすべて保持するなら O(L)O(L)、入力の指紋と頻度表が O(RN)O(RN)、積の一時キーが O(R)O(R)、素数判定用の篩と素数列が O(M)O(\sqrt M)。合計は O(L+RN+M)O(L+RN+\sqrt M) である。積のキーは一つずつ処理し、N2N^2 個を保存しない。法を先に選び、入力文字列を一つずつ指紋へ変換して捨てれば、文字列の保持は最大1000桁分で済む。

制約との対応

公式制約は 1≤N≤10001\leq N\leq1000、1≤Ai<1010001\leq A_i<10^{1000}、実行時間2秒、メモリ1024 MiB。従って L≤106L\leq10^6、N2≤106N^2\leq10^6 である。R=20R=20 なら剰余構築と積キー生成はそれぞれ高々約 2×1072\times10^7 成分分の処理になり、これに辞書の照合費用を加える。素数生成の整数提案は期待約 21.1R21.1R 回で、判定に使う素数も44721以下のものだけでよい。千桁の積を全組で持たず、短い余りの組を扱えることが制約との接続である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 乱択代数fingerprint

主題
  • 乱択代数fingerprint: multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 乱択代数fingerprint

    補助タグ: 乱択・Monte Carloアルゴリズム

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

    学習の位置

    体系上の位置: 乱択代数fingerprint

    • multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題