题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3430

题意:

对于一个1,2,3..n的序列,在给定一个置换群条件下,置换几次到达目标状态?

题解:

暴力求出各循环节与错位的次数。

得到cnt个形如 x = ci (mod mi)的方程。

其中mi并非两两互质,所以不能使用中国剩余定理。

我们可以通过类似中国剩余定理的方法求解。

使用类似数学归纳法的思想:

首先,对于同余方程 x = ci (mod mi)的一个解x。

那么x + k * mi依然是该方程的一个解。

而且同时,这样能取遍该同余方程的所有解。

我们考虑假设已经找到了一个最小自然数解x,满足了前i-1个同余方程。

那么,我们现在要让x满足第i个方程的同时,仍然满足前i-1个方程,于是我们只能取形如这样的数:x + k * LCM (其中LCM代表(m1,m2,m3...mi-1)的最小公倍数)。这样以后新的第i个同余方程变成 (x+k*LCM) = ci (mod mi)

其中x,LCM,ci,mi已知,变成 k * LCM + t * mi = ci-x。

这个方程就可以利用拓展欧几里得算法的求解。具体是调用 exgcd(LCM,mi,k,t)得出一个k*LCM+t*mi=gcd(LCM,mi)的解。

然后k*(ci-x)/gcd(LCM,mi)可以得出真正要求的式子中的k。接着就是将一个适合的k代入式子。

考虑我们在exgcd那一步求得的方程:k*LCM+t*mi=gcd(LCM,mi)。

它本质上是: k * (LCM / gcd(LCM,mi)) + t* (mi / gcd(LCM,mi))=1所以假设(k,t)是一组可行解,那么所有的可行解可以这么表示:(k + p*mi / gcd(LCM,mi) , t - p*LCM / gcd(LCM,mi))。

由于p是整数,我们可以将k%( mi / gcd(LCM,mi) )。

那么得到的数必然也是一个可行的k。(并且是最小自然数解)

这样的k自然是最合适的,我们把它代入式子。

那么得到新的x,然后再更新一下LCM,合并到最后,就得出一个最小整数解x。


#include <cstdio>
#include <cstring>

const int N = 520;
int a[N + 5], b[N + 5], ta[N + 5], tb[N + 5];
bool vis[N + 5];
long long m[N + 5], c[N + 5];

long long exgcd(long long a, long long b, long long &x, long long &y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
    long long res = exgcd(b, a % b, y, x);
    y -= a/b*x;
    return res;
}

long long mod(long long a, long long b) {
	long long res = a % b;
	if (res < 0) res += b;
	return res;
}

void solve(int n) {
	memset(vis, false, sizeof(vis));
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (!vis[i]) {
			int num = 0, t = i;
			while (!vis[t]) {
				vis[t] = true;
				ta[++num] = t;
				tb[num] = b[t];
				t = a[t];
			}
			bool same = false;
			for (int i = 1; i <= num; ++i)
				if (tb[i] == ta[1]) {
					same = true;
					int j = i, k = 1;
					do {
						if (tb[j] != ta[k]) same = false;
						j = j % num + 1;
						k = k % num + 1;
					} while (i != j);
					t = i;
					break;
				}
			if (!same) {
				printf("-1\n");
				return;
			}
			m[++cnt] = num;
			c[cnt] = (num - t + 1) % num;
		}
	
	n = cnt;
	long long ans = c[1], LCM = m[1];
	for (int i = 2; i <= n; ++i) {
		long long x, y, g = exgcd(LCM, m[i], x, y);
		if ((c[i] - ans) % g) {
			printf("-1\n");
			return;
		}
		ans = mod(ans + LCM*mod((c[i] - ans)/g*x, m[i]/g), LCM/g*m[i]);
		LCM = LCM/g*m[i];
	}
	printf("%I64d\n", ans);
	return;
}

int main() {
	int n;
	while (scanf("%d", &n), n) {
		for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
		for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
		solve(n);
	}
	return 0;
}



转载保留版权:http://haipz.com/blog/i/5820 - 海胖博客