公式解説だと各modをどう取るの？が省略されているのでその辺りの補足。
回転(rotate)する配列
この問題はindex $i$の値であるa_iをindex $a_i$にある値で置き換える操作をN回行います。
a = [0,1,2]という配列は何回置き換えても常に[0,1,2]となります。ここで、この配列をa = [1,2,0]と元のindexを一つシフトさせた(厳密には長さ$l$に対して各要素を$i+1 \mod n$とした)配列を入力したことを考えます。操作の旅に
[1,2,0] -> [2,0,1] -> [0,1,2] -> [1,2,0] ...
というように配列を回転させたようになることがわかります。この周期は$l$であるので、$N$回、回転させた時に、$N \mod l$が何であるかは判定できます。例えば、結果が[2,0,1]なのであれば、N=1,4,7,...のどれかのようにN=1+(3の倍数)であることがわかります。
回転(rotate)する部分配列を複数詰め込む
このような配列を1つの配列に複数詰め込むことを考えます。周期l_1=2の配列[1,0]と周期l_2=3の配列[1,2,0]を合わせて[1,0] + [1,2,0]のようにしたいです。このとき、それぞれの開始のindexを適切に加算し、[1,0,4,5,3]としてやります。すると、[1,0]の部分は[1,0] -> [0,1] -> [1,0] -> ...を繰り返し、[4,5,3]の部分は[4,5,3] -> [5,3,4] -> [3,4,5] -> [4,5,3]...を繰り返します。
配列全体としては、周期6となります。
[1,0,4,5,3] -> [0,1,5,3,4] -> [1,0,3,4,5] -> [0,1,4,5,3] -> [1,0,5,3,4] -> [0,1,3,4,5] -> [1,0,4,5,3]
この配列とmodの関係
周期$l$の配列を考えた時、配列の長さは$l$となり、適当な数字がどこに移動したかを$O(l)$かけて調べれば$N \mod l$の値がわかります。
ここでCRTを考えます。$k$個の$m$と$b$がある時に、
$$a \equiv b_1 (\bmod m_1) \\
a \equiv b_2 (\bmod m_2) \\
... \\
a \equiv b_k (\bmod m_k)
$$
となるaとそのmodを得られます（あるいは存在しない判定）。$m_i$の値は各周期そのもので答えが求められそうです。
M<=110の制約
ここで配列に詰め込んだ$m_i$によって得られる$mod$は)最大で$LCM(m_1, m_2, ... ,m_k)$になることに注意します。Mの制限があるのでなるべく和の少ない$m_i$で最大のLCMを得るには小さな素数を埋め込んでいけば良さそうです。LCMが$1e9$を超えるには2,3,5,..,29 が思い浮かびますがこのsumは今回の条件(110)を超えます。今回は、$m_i$同士が互いに素であれば良いため、2と３にそれぞれの素因数を１つ足して(かけて)やればよく、4,9,5..,23とすることで和が110以内の順列を作れます。
実装
入力は(a)はこれらすべての周期を含むMとaを与えて良いです。答えからのmodの復元が多少面倒に思えますが、答えの配列をすべての周期の長さ毎に切った部分配列毎に最小か最大の値の位置を適当に判定してやればよいです。CRTはACLを使うと早いでしょう。
(周期がとても小さい数であるため、私は[min,...max]が含まれる配列が何回rotationすれば一致するかを$O(N^2)$で判定しました)
実装(Python)
o =[2, 3, 4, 1, 6, 7, 8, 9, 10, 11, 12, 13, 5, 15, 16, 17, 18, 14, 20, 21, 22, 23, 24, 25, 19, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 26, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 37, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 50, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 67, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 86]
print(108, flush=True)
print(*o, flush=True)
ans = map(int, input().split())
ans = list(ans)
plist = [4,9,5,7,11,13,17,19,23]
from collections import deque
offset = 0
pl = []
for p in [4,9,5,7,11,13,17,19,23]:
ansl = ans[offset: offset+p]
ma = max(ansl)
mi = min(ansl)
l = range(mi, ma+1)
l = list(l)
l = deque(l)
k = 0
while ansl != list(l):
k += 1
l.rotate(-1)
pl.append(k)
offset += p
def egcd(a, b):
if a == 0:
return b, 0, 1
else:
g, y, x = egcd(b % a, a)
return g, x - (b // a) * y, y
def crt(bList, mList):
r, m = 0, 1
for i in range(len(bList)):
d, x, y = egcd(m, mList[i])
if (bList[i] - r) % d != 0:
return [0, -1]
tmp = (bList[i] - r) // d * x % (mList[i] // d)
r += m * tmp
m *= mList[i] // d
return [r, m]
r, m = crt(pl, plist)
print(r, flush=True)