ACG008E – Next or Nextnext

不得不说排列这类题比较需要一些想象力，需要敢想敢做。

\(p\)是一个排列，所以最后肯定形成了若干个环的形式，如果\(a\)是一个排列就很棒了，可惜\(a\)是一个普通的序列，那我们先考虑有解的充要条件。其实就是从\(p\)的环的形式推出\(a\)可能长什么样。

题目里的这个诡异的条件其实翻译一下就是在\(p\)的环里连一些边，可能连向下一个，也可能连向下一个的下一个，然后就会形成\(a\)。画个图，不难发现有下面几种情况。

• 全部连向下一点。那么\(a\)和\(p\)长得一样。
• 全部连向下一个的下一个，且\(|S| \equiv 1 \pmod 2\)。会形成另一个环。
• 全部连向下一个的下一个，且\(|S| \equiv 0 \pmod 2\)。会拆成两个环。
• 其他情况。形成一棵由一个环的若干条连在换上的链组成的内向基环树。下文的基环树全是这种特殊的基环树。

所以\(a\)只能由环和基环树组成，这样可以判掉一些简单的无解的情况。

回到原问题。我们把\(a\)形成的所有的环和基环树提取出来，显然，环的情况是可以比较容易的算出来的。

由于有合并两个大小相同的环的操作，我们考虑前求出大小为\(s\)的环有多少个，然后一起求总方案数。

设\(f_i\)表示\(i\)个大小为\(s\)的环的方案数。根据上面的前三种情况，可以比较简单地转移。

下面考虑有基环树的情况的方案数统计。我们需要时刻记住\(p\)是一个排列，这意味着\(p\)只能由环组成。因此，我们要把基环树中的链强行塞到环里。

注意到环上入度为\(2\)的点是很特殊的，因为它后面不能塞链上的点。所以可以考虑以这样的点为分界算方案数。

试着画个图看看，发现我们必须这样塞：除去开头的链上的点和原本环上的点是交错排列的。所以考虑设\(l_1\)表示链的长度，\(l_2\)表示这一段的长度。

• \(l_1 < l_2\) 意味着开头随便填，链上第一个点可以和开头相邻，也可以不相邻，那就是\(2\)种方案
• \(l_1 = l_2\) 意味着链上第一个点只能和开头相邻，因为最后一个点顶到上一段的开头了。
• \(l_1 > l_2\) 怎么填的填不进去，无解。

直接模拟这个过程，复杂度\(O(n)\)。

#include <cstdio>
#include <iostream>
#include <cstring>
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
	x = 0; int f = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
	if(f) x = ~x + 1;
}
const int P = 1e9 + 7;
const int N = 2e5 + 10;
int n, a[N], d[N], vis[N], cir[N], cnt[N], sz[N], beg[N], id[N], l[N], tag[N], f[N];
int main() {
	read(n);
	for(int i = 1; i <= n; ++i) 
		read(a[i]), ++d[a[i]];
	for(int i = 1; i <= n; ++i) {
		if(vis[i]) continue;
		int x = i; 
		while(!vis[x]) vis[x] = i, x = a[x];
		if(i != vis[x]) continue;
		while(!cir[x]) cir[x] = 1, x = a[x];
	} 
	for(int i = 1; i <= n; ++i)
		if((cir[i] && d[i] > 2) || (!cir[i] && d[i] > 1))
			{puts("0"); return 0;}
	memset(vis, 0, sizeof(vis));
	int tot = 0;
	for(int i = 1; i <= n; ++i) {
		if(vis[i]) continue;
		if(cir[i]) {
			int x = i, len = 0;
			++tot;
			while(!vis[x]) vis[x] = 1, ++len, id[x] = tot, x = a[x];
			sz[tot] = len, beg[tot] = i;
		}
	}
	for(int i = 1; i <= n; ++i) {
		if(!cir[i]) {
			if(d[i]) continue;
			int x = i, len = 0;
			while(!cir[x]) vis[x] = 1, ++len, x = a[x];
			l[x] = len, tag[id[x]] = 1;
		}
	}
	int ans = 1;
	for(int i = 1; i <= tot; ++i) {
		if(!tag[i]) {++cnt[sz[i]]; continue;}
		int x = beg[i], cur = 1;
		while(!l[x]) x = a[x];
		beg[i] = x; x = a[x];
		while(x != beg[i]) {
			if(l[x]) {
				if(l[x] < cur) ans = 2 * ans % P;
				else if(l[x] > cur) {puts("0"); return 0;} 
				cur = 0;
			}
			++cur;
			x = a[x];
		}
		if(l[x]) {
			if(l[x] < cur) ans = 2 * ans % P;
			else if(l[x] > cur) {puts("0"); return 0;}
		}
	}
	for(int i = 1; i <= n; ++i) {
		f[0] = 1;
		for(int j = 1; j <= cnt[i]; ++j) {
			if(i > 1 && (i & 1)) f[j] = 2 * f[j - 1] % P;
			else f[j] = f[j - 1];
			if(j > 1) f[j] = (f[j] + 1ll * (j - 1) * f[j - 2] % P * i % P) % P;
		}
		ans = 1ll * ans * f[cnt[i]] % P;
	}
	printf("%d\n",ans);
}

原文地址：http://www.cnblogs.com/DCH233/p/16923539.html