yukicoder contest 283 G 誕生日プレゼント 別解解説

　writer解・tester解と異なる方法で解いたので紹介します。

問題

yukicoder contest 283 G ★4.5 誕生日プレゼント
問題リンク：https://yukicoder.me/problems/no/1404

要約：
　長さ $N$ の整数列 $A$ , $B$ が与えられるので、次の操作を合計 $P$ 回以下行って $A$ を $B$ に一致させよ。不可能ならそれを報告せよ。

• 操作 $1$ : $i,j$ を選んで $A_i$ に $A_j$ を加算。
• 操作 $2$ : $A$ の要素すべてに $\mathrm{mod} \ P$ を適用する。

制約：

• $1 \le N \le 10^5$
• $P=223577$ ( 素数 )
• $0 \le A_i, B_i \lt P$

解説

利用する有名テクニック一覧

• ダブリング・繰り返し二乗法
• $\mathrm{mod}$ 素数における四則演算
• 平方分割

簡単な場合分け

操作 $2$ は最後に $1$ 回だけ行う。
$A$ または $B$ がすべて $0$ の場合と、 $N=1$ の場合を排除できる。

　操作 $2$ を最後に行うことにすれば、途中の操作 $1$ をすべて $\mathrm{mod} \ P$ で行うものとしてよいです。以下、操作 $1$ は $\mathrm{mod} \ P$ で行い、途中の操作 $2$ は考えません。

　$A$ がすべて $0$ のとき、 $B$ がすべて $0$ なら $0$ 回の操作で目的が実現可能で、そうでなければ実現不可能です。逆に、 $B$ がすべて $0$ で $A$ が「すべて $0$ 」ではない場合は、 $B$ から始めて本来と逆の操作を考えると、実現不可能であることがわかります。

　$N=1$ のとき、唯一可能な操作「 $A_1$ に $A_1$ を足す」を $P-1$ 回繰り返す間に、 $B$ に一致するか確かめます。試してみると $2^{(P-1)/4} \equiv 1 \ ( \mathrm{mod} \ P )$ より $(P-1)/4$ 回で $A_1$ の値が元に戻るので、操作 $1$ は $(P-1)/4-1$ 回以下になります。

任意の値を $36$ 回の操作で生成

$A_i \ne 0$ ならば、 $36$ 回以下の操作で $A_j$ $( i \ne j )$ を任意の値にできる。

　$A_1 = 0 , A_2 = 1$ のとき、操作 $\mathrm{X}$ 「 $A_1$ を $2$ 倍して、 $A_2$ を $A_1$ に $0$ 回か $1$ 回足す」 を $K$ 回繰り返すと、 $A_1$ を $0$ 以上 $2^K-1$ 以下の任意の整数にできます (ダブリング) 。操作はそのままで $A_1 = s , A_2 = t$ とすると $A_1$ を $2^K s + t x$ $( \mathrm{mod} \ P )$ ( $x$ は $0$ 以上 $2^K-1$ 以下の整数 ) にできます。 $K$ が $P \le 2^K$ を満たし、 $t \ne 0$ であれば、この値の集合は $0,1, \dots ,P-1 \ ( \mathrm{mod} \ P )$ をすべて含みます。

　目的の値 $k$ のために操作の手順を復元するには $x$ の値が必要ですが、 $k = 2^K s + t x$ を $x$ について解くと $x = ( k-2^K s ) / t$ で求まります。

　$2^K \le P$ のためには $K = 18$ でよく、操作 $\mathrm{X}$ は、 $2$ 回以下の操作 $1$ で再現できるので、この手順全体は $36$ 回でできます。

値の平方分割

$N$ が大きいとき、 $N$ が $1$ 増えると操作回数が高々 $2$ 増える。

　考えられる方針は複数ありますが、値を平方分割すればうまくできます。

　$\sqrt{P} \le 500$ を考えます。数列 $A$ 中に $1,2,3, \dots ,499$ と $500,1000,1500, \dots ,500 \times 499$ を出現させ、他の要素に適宜足すことで、他の要素 $1$ つあたり高々 $2$ 回の操作で $B$ と一致させられます。これを次の手順で実現します。

• $A_1 = 1 , A_2 = 1$ とする。
• $A_1$ に $A_2$ を足す操作を $A_1 = 499$ まで繰り返しながら、適宜 $A_3$ ～ $A_N$ に $A_1$ を足す。
• $A_1 = 500 , A_2 = 500$ とする。
• $A_1$ に $A_2$ を足す操作を $A_1 = 500 \times 499$ まで繰り返しながら、適宜 $A_3$ ～ $A_N$ に $A_1$ を足す。

　この手順は $2N + 500 \times 2 + 36 \times 4 \le 201144$ 回以下の操作で実現可能です。

後片付け・まとめ

　$A_1$ と $A_2$ は $B$ と関係ない値になっているので、操作 $\mathrm{X}$ を用いて合わせます。

　以上、平方分割→後片付けで目的を必ず達成できます (上の「簡単な場合分け」で排除した場合を除く)。

　時間計算量は $O ( N + P )$ 、操作回数は $2N + 2 \sqrt{P} + O( \log P )$ です。

提出コード

提出コードのリンク：https://yukicoder.me/submissions/620527

　操作回数は

• $N=1$ のとき高々 $\{ (P-1)/4-1 \} + 1 = 55894$ 回
• $2 \le N$ のとき高々 $10^5 \times 2 + 500 \times 2 + 36 \times 8 + 2 + 1 = 201291$ 回

となり、 $201291$ 回以下です。