『湖南省队集训』DeepDarkFantasy

题目

从东京出发，不久便到一处驿站，写道：日暮里。 ——鲁迅《藤野先生》

定义一个置换的平方为对$1 \sim n$的序列做两次该置换得到的序列。已知一个置换的平方，并且这个结果是一个排列， 求该置换。

输入第一行一个数$n$表示排列长度， 接下来一行$n$个数描述排列。

有解则输出一行$n$个数表示原排列。 否则输出一行一个$-1$。

测试点编号	特征
$0 \sim 1$	$n \leq 10$
$2 \sim 9$	$n \leq 1000000$

此题有spj。

题解

首先要解释清楚题意对吧，题面中置换和排列真是乱七八糟。

大意就是，初始排列是$(1, 2, \dots, n)$，你要构造一个置换，然后对这个排列进行置换，把得到的排列再进行一次置换，得到的结果为给定排列。举个例子，假设$n=4$，我们构造的置换是$\begin{pmatrix}1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1\end{pmatrix}$，那么置换一次得到$(4, 3, 1, 2)$，再做一次得到$(2, 1, 4, 3)$，这就满足样例了。

我们再回顾一下置换的定义，就是把一个序列中的每个数放到一个指定的位置，而给出的排列则是每个位置上的数。因此，我们求出给出排列的逆，就得到了每个数所在的位置，也就是另一个置换。这时，就可以形象地说，我们要把置换“开方”，解除连做两次等于它的一个置换。

根据基本知识，一个置换可以分解成若干个循环。这些循环中，长度为奇数的循环是可以直接开方的，因为走两次向右移了一步，等价于每一次向右移$\frac{len+1}{2}$步，因此每个元素对应的结果就是在它后面这么多位的元素。长度为偶数的则需要找一个和它长度一致的，然后交叉合并就好了。这里不是很容易说清楚，还是画个图理解一下吧。

注意代码实现，最好保证排序、找等长循环等步骤严格线性，不然容易T。

代码

#include <cstdio>
#include <cctype>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1000010
int readint()
{
    int x = 0, c;
    while (!isdigit(c = getchar()));
    do
        x = x * 10 + c - '0';
    while (isdigit(c = getchar()));
    return x;
}
int n;
int ff[MAXN], f[MAXN];
bool vis[MAXN];
vector<int> round[MAXN];
int cnt;
int temp[MAXN];
int times[MAXN];
inline void work(int st)
{
    while (!vis[st])
    {
        vis[st] = 1;
        round[cnt].push_back(st);
        st = ff[st];
    }
    cnt++;
}
stack<char> put;
inline void printint(int x)
{
	while (x)
	{
		put.push((x % 10) + '0');
		x /= 10;
	}
	while (!put.empty())
	{
		putchar(put.top());
		put.pop();
	}
}
int main()
{
    freopen("deepdarkfantasy.in", "r", stdin);
	freopen("deepdarkfantasy.out", "w", stdout);
    n = readint();
    for (int i = 1; i <= n; i++)
    {
    	int x = readint();
    	ff[x] = i;
	} 
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
        if(!vis[i])
            work(i);
    for (int i = 0; i < cnt; i++)
    	times[(int)round[i].size()]++;
    for (int i = 1; i <= n; i++)
    	times[i] += times[i - 1];
    for (int i = 0; i < n; i++)
    	temp[--times[(int)round[i].size()]] = i;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < cnt; i++)
    {
        int sz = (int)round[temp[i]].size();
        if (sz & 1)
        {
            for (int j = 0; j < sz; j++)
                f[round[temp[i]][j]] = round[temp[i]][(j + (sz + 1) / 2) % sz];
        }
        else
        {
        	if (vis[temp[i]])
        		continue;
            if (i >= cnt - 1 || sz != (int)round[temp[i + 1]].size())
            {
                printf("-1\n");
                return 0;
            }
            int t = temp[i + 1];
            for (int j = 0; j < sz; j++)
                f[round[temp[i]][j]] = round[t][j], f[round[t][j]] = round[temp[i]][(j + 1) % sz];
            vis[temp[i + 1]] = true;
        }
    }
    for (int i = 1; i <= n; i++)
    {
    	printint(f[i]);
    	if (i < n)
    		putchar(' ');
    	else
    		putchar('\n');
	}
    return 0;
}