Problem: L题 Three Permutations

题意

• 给三个长度都为n的数组a, b, c。
  
• 定义一种对于三元组$(x,y,z)(x,\; y,\; z)$的更新操作为：$(x,y,z)->(a[y],b[z],c[x])(x,\; y,\; z)\; ->\; (a[y],\; b[z],\; c[x])$。
  
• 本题会有q次查询，每次查询给出一个三元组$(x,y,z)(x,\; y,\; z)$。问最少需要多少次操作可以使得三元组$(1,1,1)(1,\; 1,\; 1)$变成给出的$(x,y,z)(x,\; y,\; z)$。

思路

多玩几次这个更新操作，发现对于三元组$(x,y,z)(x,\; y,\; z)$可以变成这样的形式$(a[b[c[x]]],b[c[a[y]]],c[a[b[z]]])(a[b[c[x]]],\; b[c[a[y]]],\; c[a[b[z]]])$。看到上面的三元组，发现在三次操作后$x,y,zx,\; y,\; z$又回到了最开始的位置。故我们对于一个可以定义一个$xx$的函数$f(x)=b[c[x]]f(x)\; =\; b[c[x]]$，表示每三次翻转后x的值。

又因为数组$a\mathrm{、}b\mathrm{、}ca、b、c$长度有限，同时其内值都是1~n范围内，所以对于无限次的三次操作一定是有一个循环节。我们可以找到对于每个起点$x=1,x=a[1],x=a[b[1]]x\; =\; 1,\; x\; =\; a[1],\; x\; =\; a[b[1]]$的最小循环周期$m1m1$和其循环周期内每个数在第几$(r1)(r1)$次操作后出现。我们就可以通过解方程$x\equiv r1(modm1)x\; \backslash equiv\; r1\; (mod\backslash \; m1)$找到对于任意的值,它如果在多次操作后出现,他出现在第多少次.

对于上面发现$b,cb,\; c$数组也是同理. 故对于多少次从$(1,1,1)(1,\; 1,\; 1)$变成给出的$(x,y,z)(x,\; y,\; z)$, 我们只需要联立三个同余方程求解即可.

解题方法

容易发现我们联立的同余方程组的模数不一定是两两互质的, 因此我们求解这个方程组应该使用拓展中国剩余定理$(excrt)(excrt)$.

如果我们直接按照上述思路找到三个起点的周期及周期内每个数出现的最少操作数, 是可以得到本题的解. 但我们也可以进行一定的优化:
我们求出$(1,1,1)(1,\; 1,\; 1)$的同余方程，对于$(a[1],b[1],c[1])(a[1],\; b[1],\; c[1])$和$(a[b[1]],b[c[1]],c[a[1]])(a[b[1]],\; b[c[1]],\; c[a[\; 1]])$。我们可以翻过来将目标数组反操作，使得从求$(a[1],b[1],c[1])(a[1],\; b[1],\; c[1])$和$(a[b[1]],b[c[1]],c[a[1]])(a[b[1]],\; b[c[1]],\; c[a[\; 1]])$变为求$(1,1,1)(1,\; 1,\; 1)$。详情可以看代码中查询处的处理。

复杂度

• 时间复杂度:

需要用到拓展欧几里得算法，复杂度是$O(nlogn)O(nlogn)$

• 空间复杂度:

只开了线性空间，复杂度是$O(n)O(n)$

Code

#include <bits/stdc++.h>

#pragma GCC optimize(2)
using namespace std;

#define endl "\n"
#define ll long long
#define pll pair<long, long>

//板子
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
    if (!b) d = a, x = 1, y = 0;
    else exgcd(b, a % b, d, y, x), y -= a / b * x;
}

pll excrt(pll l, pll r) {
    auto[r1, m1] = l;
    auto[r2, m2] = r;
    if (r1 == -1 || r2 == -1) return {-1, -1};

    ll d, l1, l2;
    exgcd(m1, m2, d, l1, l2);
    if ((r2 - r1) % d) return {-1, -1};

    l1 = ((l1 % (m2 / d) + m2 / d) % (m2 / d)) * (((r2 - r1) / d) % (m2 / d));
    l1 = (l1 % (m2 / d) + m2 / d) % (m2 / d);

    ll L = m1 / d * m2;

    ll R = (((l1 % L) * (m1 % L) % L + r1 % L) % L + L) % L;
    return {R, L};
}

//解
void solve()
{
	//输入三个数组
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1), c(n + 1), ia(n + 1), ib(n + 1), ic(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i], ia[a[i]] = i;
	for(int i = 1; i <= n; i++) cin >> b[i], ib[b[i]] = i;
	for(int i = 1; i <= n; i++) cin >> c[i], ic[c[i]] = i;

	//处理循环周期和到每个位置的最小操作数
	vector<int> dista(n + 1, -1), distb(n + 1, -1), distc(n + 1, -1);
	int lena = 0, lenb = 0, lenc = 0;
	for(int u = 1; dista[u] == -1; u = a[b[c[u]]], lena++) dista[u] = lena;
	for(int u = 1; distb[u] == -1; u = b[c[a[u]]], lenb++) distb[u] = lenb;
	for(int u = 1; distc[u] == -1; u = c[a[b[u]]], lenc++) distc[u] = lenc;

	//处理同余方程组
	auto EXC = [&](int iA, int iB, int iC) -> ll{
		if(dista[iA] == -1 || distb[iB] == -1 || distc[iC] == -1) return 1e18;

		pll A(dista[iA], lena), B(distb[iB], lenb), C(distc[iC], lenc);
		A = excrt(A, excrt(B, C));
		return A.first == -1 ? 1e18 : A.first;
	};

	//处理查询
	int q;
	cin >> q;
	while(q--){
		int x, y, z;
		cin >> x >> y >> z;
        //计算到达目标三元组的最小操作数
		ll mn = min({3 * EXC(x, y, z), 1 + 3 * EXC(ic[z], ia[x], ib[y]), 2 + 3 * EXC(ic[ib[y]], ia[ic[z]], ib[ia[x]])});
		cout << (mn >= 1e18 ? -1 : mn) << endl;
	}
}

int main()
{
	cout.tie(nullptr);cin.tie(nullptr);ios::sync_with_stdio(false);
	
	solve();

	return 0;
}

欢迎大家批评指正