AGC003

A Wanna go back home

= =

直接腾讯。

考虑将(a)分成(L=a[::2])和(R=a[1::2])，这两个序列可以不消耗代价随意打乱，或者可以交换(L_i)和(R_i)

所以如果从两个序列中分别拿出一个元素交换代价是(1)

计算有多少起始序列!=目标序列的数，答案就是(lfloor cnt/2 floor)

对每个数(x=Pi p_i^{e_i})，将其变成最简形式(Pi p_i^{E_i=e_imod 3})不影响答案

然后一个数(x=Pi p_i^{E_i})对应的满足(xy)是完全立方数的(y)只有一个，那就是(Pi p_i^{-E_imod 3})

对每个数计算一下出现了几次，如果它和另一个数互斥，则删掉数量较小的那一堆

（特判一下，如果有一堆化简后是(1)就代表都是完全平方数，会和自己互斥，这一对只能随便选(1)个）

毒瘤

对于缩小操作，那么前面一些操作会没用，先用一个单调栈去除掉无用操作，这样(q)就单调递增了

从后往前考虑，每次拿出最后一个操作，计算它对答案的贡献

(q_i)会从(q_{i-1})循环复制过来，就会被分成很多个(q_{i-1})和一段前缀

维护一个(mul_i)，这差不多是一个标记，表示最后的序列会加上(mul_icdot A[1,q_i])

（最后序列加上(kcdot A[1,r])的意思是会再出现(k)个和(A[1,r])一样的数

具体要实现这样一个函数：(work(p,M))，表示最后序列加上(Mcdot A[1,p])

如果(pleq q_1)（(q_1)一定不大于(n)）那么(ans_1)到(ans_p)要加上(M)；

否则和前面一样的，找到第一个可行的操作，然后递归下去

具体看代码= =

神题Orz

首先特判掉一些情况：

现在只有一种情况：左右连通（上下的话翻过来

1e18显然要矩乘dp，设(f_{i,0})表示(i)层分形图的连通块数，(f_{i,1})表示（（在当前图形最左有东西）和（如果左右拼这个图形，该连通块会和更左边一个连通块拼接(这个连通块可能是自己也可能是原来最右边的连通块)））的(x)连通块数

现在是转移，

(f_{i,1}=f_{i-1,1} imes c)，(c)为在初始图形最左和最右都有东西的(x)坐标数

(f_{i,0}=f_{i-1,0} imes cnt_1-f_{i-1,1} imes a)，(a)为初始图形左右相邻两个坐标都是1的方案数

就可以矩乘了