(※以下、桁は2進数での桁を表し、小さい方から(1,2,4,8,16,… を表す桁の順に)1,2,3,… 桁目とする)
再帰で分割していく。
もし、$A$ の中で $d$ 桁目が'0'のものと'1'のものが混在していたら、 どのように $x$ を選ぼうと、$B$ でも'0'と'1'が混在してしまう。
逆に、全て'0'か全て'1'なら、$B$ の全てで必ず $d$ 桁目は'0'にできる。
それを踏まえて、上位bitから考える。
いま、$A$ の中で0と1が混在しているような最上位桁を $d$ とする。
すると、$B$ の最大値も $d$ 桁にならざるを得ない。
$A$ を「$d$ 桁目が0であるグループ」「1であるグループ」に分割すると、 同じグループの操作後の $d$ 桁目は同じになる。
さて、どちらのグループの操作後の $d$ 桁目を0にし、どちらを1にすべきか?
操作後の $d$ 桁目が0になるグループは、その時点で必ず1になるグループより小さくなることが確定するので、
$d-1$ 桁目以降がどんなに大きくなってもかまわない。
$x$ を決める際は、1になるグループの $d-1$ 桁目以降を最小化することに注力すればよい。
よって、それぞれのグループで $d-1$ 桁以降のみで全体と同じ問題を解き、「もしこっちのグループを1にした場合、最小値はいくつになる?」を調べる。
その結果、最大値が小さくなる方を、操作後に $d$ 桁目が1となるようにすればよい。
d桁目 v グループ 00101101 -, _0101101 グループ0のみで 01010101 | 0 → _1010101 全体と同じ問題を解いた答えをpとする 01101110 -' _1101110 10111000 -, 11100011 | 1 ┐ _0111000 グループ1のみで 11001100 -' └> _1100011 全体と同じ問題を解いた答えをqとする _1001100 p <= q なら、グループ0の操作後のd桁目が 1 となるようにし、答えは 10000000 + p p > q なら、グループ1の操作後のd桁目が 1 となるようにし、答えは 10000000 + q
これを再帰的に処理すれば良い。
処理の途中でグループのサイズが1個になったら、 後はその1個が操作後に完全に0になるような $x$ を選べば良いので、(分割問題の答えは $0$) 以降の桁は探索を打ち切れる。
仮に打ち切らず最終桁まで処理したとしても、$N$ 個の要素がそれぞれ $\log_2{A_i}$ 回、 bitが0か1かチェックされたり分割されたりすることになるので、$O(N \log{A_{max}})$ で処理できる。
$M$ が素数とは限らないので、いつもの逆数modや、FFTによる畳み込みは使えない点に注意。
まぁ $N$ が小さいので、二項係数 ${}_nC_r$ なんかは $n \le N$ の範囲なら事前計算してしまえる。
素直(?)に考えると3次元DPで遷移にも $N$ かかって $O(N^4)$ 解法が思いつくが、 実は1次元省略して $O(N^3)$ にできる、という問題。
距離 1 2 ... i ①--○--○- ... -○ `-○ ` ... -○ -○ ↑ ...k個 └─────────┘ ...j個
ここに、最短距離が $i+1$ の頂点を $l$ 個追加することを考える。
これらを掛け合わせたものとなる。
実は、遷移の式を見ても $i$ が出てこないことからもわかるとおり、$i$ の次元は省略できる。
最短距離が異なっていても「今までに $j$ 個使って、そのうち直前が $k$ 個」という情報さえ一致していれば同じ遷移ができる。
さて、$j=N-1$ まで埋め終えたとして、最後に頂点 $N$ との辺を考慮しつつ合計する。
末尾 $k$ 個と頂点 $N$ 間の辺の張り方は、上記②の考え方と同じく $2^k-1$ 個ある。
$DP[N-1,k] \times (2^k-1)$ を $k=1,...,N-2$ で合計すれば答え。