道筋の立て方はまぁ自然かなと思う。実装は重め。
木なので、どう足掻いても $M$ 頂点を順番に訪問するのに通る経路、ひいては各辺を使う回数は固定である。
全行程で $D_i$ 回使う辺を赤に塗れば、最終的な $R-B$ には $+D_i$ だけ寄与するし、青に塗れば $-D_i$ だけ寄与する。
こうすれば後は、どの辺を+で寄与させ、どの辺をーで寄与させるかのDPになる。
①は、1回1回BFSなりDFSなりすればよい。
使った辺を特定する必要があるので、経路復元を可能にしておく。
たとえば、各頂点に「この頂点に到達するのに使用した辺」を記録しておけば、ゴールから遡りながら復元できる。
②のDPは、$DP[0][0]=1$、他は $0$ で初期化し、各 $i,j$ につき以下のように遷移する。
これ、計算量を考えるとちょっと不安になる。
1辺あたりのカウントの最大値は $M$ 回だが、$j$ が取り得る範囲としてはその総和、つまり $j=-NM~NM$ の範囲を取り得る。
$i=0~N-1$ の範囲を動くので、DPの計算量は工夫無しでは $O(N^2M)$、制約上限を代入すると $10^8$ となる。
Pythonなどの遅い言語では、もう少し高速化を試みたい。
また、以下のような方法もある。
■各Diに+か-を割り当てて合計がKになるようにする (達成できる一例) + D1 - D2 - D3 + D4 + ... + D[N-1] = K 両辺に S = D1+D2+D3+...+D[N-1] を足す + 2*D1 - 0 - 0 + 2*D4 + ... + 2*D[N-1] = K + S 2で割る D1 + D4 + ... + D[N-1] = (K + S) / 2 つまり、各Diに+か-を割り当てて合計がKになる割り当て方があると、 それの「+を割り振ったもののみの合計」は、必ず (K + S) / 2 になる。 (上では一例を取りだして説明したが、他の例でも必ずそうなる)
従って、「$D_i$ からいくつかを選んでその和が $\dfrac{K+S}{2}$ になる方法の個数」を数えればよいことになる。
こうすると、遷移は以下のようになるので、
DP配列は実装上、$i$ の次元を省略し、1つ前の状態に $D_i$ だけシフトしたものを足し込んでいく、という形にできる。
計算量のオーダーは変わらないものの、Pythonでは特にNumpyを使って高速化しやすい形にできる。
-1
と答えよなんかABC174と似ていたらしい。みんなよく覚えてるな。
ただ、ABC174では1つのケースだけ求められれば良かったので 「割り算の筆算シミュレーション」的な解法が使えたが、最悪 $O(K)$ かかるので今回は無理。
より高速に求める方法を用いる。
まず大まかな場合分けとして、
これで全ての $K$ について同等の条件を調べればよくなった。
ここで、999…9 を $10^n-1$ という形で表現できることを使うのが、このような問題における典型アプローチっぽい。
従って、以下のように言い換えられる。
これ、考え方はlogと同じであり、modの世界におけるlogは離散対数問題と呼ばれている。
$X^n \equiv Y \mod{M}$ となる最小の $n$ を求めたいとする。
解が無い場合もあるが(場合分けは上記記事参照)、存在する場合は鳩ノ巣原理で $0 \le n \lt M$ の範囲で必ず見つかる。
従って、平方分割の容量で $\sqrt{M}$ ずつ枠をずらしながら考える。この手法はBaby-step Giant-stepと呼ばれる。
X = 10 Y = 1 M = 171 n 1 2 3 4 5 ... 14 15 ... 28 29 ... 170 X^n 10 100 145 82 136 ... 73 46 ... 28 109 ... 55 この中に、10^n = 1 となる正整数 n があるはず。 √171 ≒ 14 なので、1~14, 15~28, 29~42, ... ごとに探していく。
まず、$n=1~14$ を愚直に求め、辞書などで $10^n$ から $n$ を逆引きできるようにしておく。
この中に $10^n=1$ となるものがあれば、それが答え。
無い場合、$Y$ の方をずらす。つまり、mod上で $Y$ を $X^{-14}$ 倍する。
この時、mod逆数が存在するかどうかで少しややこしくなるが、 今回は $X=10$ と $M$ が互いに素でない($M$ が2や5の倍数)なら不可能であることがわかりやすいので、 最初に場合分けしてしまえば残りは必ず存在する。
$1 \times 10^{-14} \equiv 82 \mod{171}$ となる。
次は、逆引き辞書から $82$ を探せばよい。
すると $n=4$ の時が見つかる。
$14$ ずらした結果 $n=4$ の時に見つかったので、$n=18$ が答えとなる。$10^{18} \equiv 1 \mod{171}$
辞書の内部実装によるが、値の検索が $O(1)$ でできるなら、1つの $K$ につき $O(\sqrt{K})$ で求められる。