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 $ 回以下です。