考察
二つの基数をすべて試すには範囲が大きすぎる。そこで、同じ桁列を二通りに評価した「差」に注目する。基数の差は与えられた差の約数に限られ、さらに各桁の重みが下位桁全体の最大寄与を上回るため、基数を固定すれば桁を高位から一つずつ確定できる。
基数の差を固定し、長さで分ける
桁列を とする。 ならどの基数でも値は なので、正の差 は作れない。 では、先頭桁が正で他の桁も非負であるため、基数を大きくすると値は厳密に増える。従って解では である。また では全桁が0に制限され、先頭桁を正にできない。以降は とし、
と置く。各桁の範囲は 、差の条件は
となる。 なので末尾桁は差に影響しない。一方、 では冪差の因数分解により だから、必ず である。大きい そのものを走査する代わりに、小さい の約数を列挙する方針が見えてくる。
まず では、先頭桁を とすると条件は だけになる。 のうち を満たすものを試せば、 が決まる。先頭桁の上限と を合わせた範囲は
である。各 について末尾桁は 通りなので、 のとき
を加える。ただし非負整数 に対し、
である。 なら加算は0とする。これで、二桁では の候補が巨大でも区間和で処理できる。
次に を考える。先頭桁が1以上なので であり、
が必要になる。従って の約数 ごとに、
だけを列挙すればよい。上端が2未満なら候補はない。この範囲は が大きくても だけで抑えられる。残る課題は、一つの基数対について桁列をどう調べるかである。
一つの重みは下位桁全体より大きい
通常の位取り表記では、下位桁をすべて最大にしても一つ上の位に届かない。その性質が、今回の重み にもあれば、高位から商を取る方法が使える。そこで、まず桁上限を とした下位桁の最大寄与と比べる。
に対して等比級数を展開すると、
だから、その差を使って
を得る。実際の上限は なので、
も成り立つ。 で桁上限が9になる場合も、同じ証明を使える。
商が桁を強制する理由
高位の桁を処理した後の残余を とする。残る指数が 以下なら、解が存在するためには
と書ける必要がある。ここで は指数 の桁、 は下位桁の寄与である。従って
が強制される。商を一つ減らすと下位桁へ 以上を渡すことになり、最大寄与を超える。商が 以上のときも、合法な小さい桁へ置き換えて下位桁で埋めることはできない。
具体的には、 を満たす最大の指数を とし、 から の順に商を求める。どこかの商が 以上なら不可能、そうでなければ を に更新する。最後の残余が0なら、選んだ桁の寄与の和がちょうど なので十分でもある。指数0の桁で余りを埋めることはできない。
例えば なら 、重みは となる。
- では商は指数2で1、残余1、指数1で1、残余0となる。末尾を除く桁列は に決まり、末尾を0または1として の2通りを得る。
- では指数2の桁を1にした残余が2で、指数1の商2が桁上限に反する。指数2の桁を0にしても、下位の最大寄与は1なので救えない。
最大指数 より大きい桁は、1以上なら重みだけで を超える。一方、 未満の桁だけでは最大寄与が に届かない。従って解の先頭の指数は必ず 、先頭桁は正である。三桁以上の列挙では を確認し、復号に成功した基数対ごとに末尾桁の選択数 を加える。高々一つなのは末尾を除く桁列であり、末尾まで含む列は 通りある。
典型の発動条件
差の因数による候補圧縮
巨大な二つの整数について多項式評価の差が小さい値に固定されるなら、共通因子となる二整数の差を探す。本問では に加え、三桁以上の先頭項から二乗差の上限を得た。二桁のようにこの上限を使えない場合は分けて直接数える。
superincreasing weightのgreedy復号
各重みが「合法な下位係数による最大総和」を上回るなら、高位の商が唯一の係数になる。この性質を満たす重みを superincreasing な重みと呼ぶことがある。単に重みが増加するだけでは不十分であり、下位の最大総和との厳密な不等式を証明してから使う。
自由な零weight桁の分離
係数の重みが0なら、その係数は目標値から復元できない。他の係数を確定させた後、合法な選択数を掛ける。ただし他の制約にも影響しないことを確認する。本問の末尾桁は先頭桁ではなく、桁上限以外の制約を持たない。
問題固有の要素
同じ桁列を異なる基数で評価する条件から、冪差を重みにした表現が現れる。この重みは基数差で割り切れるだけでなく、桁上限と組み合わせると下位の最大寄与を上回る。差の因数分解で候補を減らし、残った候補内では表現の一意性を使う、という二段階を見抜くことが核心である。
正当性
では差が0となる。 の解では、非負の桁と正の先頭桁から が必要である。二桁の解は先頭桁 と 、区間 の選択に一対一に対応し、末尾の選択数は である。三桁以上の解は かつ を満たすため、指定した約数と基数の列挙から漏れない。
各基数対では、 と より、合法な下位桁の寄与は 未満である。従って存在する解の各桁は高位から取る商に強制され、商が 以上なら解はない。すべての商が合法で最終残余が0なら、その桁列は差の条件を満たす。先頭の指数は を満たす に限られるので、末尾を除く桁列は高々一つである。
三桁以上では を要求し、自由な末尾桁の 通りを加える。二桁と三桁以上は重ならず、異なる基数対は別の組なので、加算結果は求める全組数となる。
実装上の注意
- や では を満たす対がなく、答えは0となる。列挙の下端を2とし、空区間を処理すれば自然に除外できる。
- 答えは で割った余りを取る。二桁の区間和は64 bit整数で計算してから加算すればよい。
- 重み は 以下のものを指数1から保存し、初めて を超えたところで止める。等号の場合は保存する。 では割り算せず、最後の残余と末尾の自由度を別に処理する。
冪をそれぞれ に飽和させてから引いてはいけない。例えば では、 を求めたいのに、飽和後の差は となる。代わりに、正の項だけからなる
を使う。 なので、この漸化式は正確である。乗算前の判定まで含めた生成手順は次のようにできる。
- 現在の と を保持する。初期値は 、 とする。
- なら次の重みは を超えるので停止する。そうでなければ を計算する。
- なら停止する。そうでなければ を計算して保存する。 に飽和していた場合は必ず停止するため、保存する差は常に正確である。
- 次の反復のため、 なら 、そうでなければ と更新する。
これなら超過する積を実際に作らずに済む。 で重みは増え続けるため、一度超えた後の指数もすべて除外できる。復号は保存した重みを逆順に使い、三桁以上の処理では最大指数が2以上であることを確認する。
復習の核
- 候補の上限が巨大でも、差が小さいなら因数分解から「差の約数」を列挙できないか考える。
- 高位から商を取るには、下位桁の最大寄与が現在の重み未満であることを示す。単調増加や典型名だけで正当化しない。
- 重み0の桁は一意復号の対象から外し、自由度として数える。差を計算するときも、二つの値を個別に飽和すると相殺を壊すことに注意する。
計算量と制約
時間
約数は 時間で列挙でき、二桁の処理は先頭桁9通りで 時間である。三桁以上の基数対の総数を とすると、各約数 に対して だから、
と だけで評価できる。各対では より重みの生成と復号がともに 時間なので、全体は 時間となる。
空間
約数一覧に 、一つの基数対の重み列に を使う。ここで は の約数の個数である。基数対や桁列をすべて保存する必要はなく、全体は 空間である。
制約との対応
に対して基数対の全探索はできないが、 なので、二桁を区間和で処理し、三桁以上の候補と重み数を で制限できる。時間制限は2秒、メモリ制限は1024 MiBである。正の 、非負の桁、正の先頭桁、 がそれぞれ候補の制限と復号の証明に必要である。
出典