bzoj 3990 排序

Posted on | Views:

爆搜乱搞.

首先可以注意到,操作的顺序是没有影响的.

从小到大考虑每个操作,若操作了 $k$ 次,且最后合法,则这种方案对答案的贡献为 $k!$ .

在第 $i$ 次操作时,我们把序列分成 $2^{n-i}$ 段,每段长度为 $2^i$ ,则可以交换两个 “半段” .

考虑那些不是连续递增的段,必须在当前这次操作处理,否则之后就被合在一起,无法处理了.

若没有这样的段,则不执行操作.

若有 $1$ 个这样的段,就将该段的前后两部分交换,若合法则继续,否则这种情况没有贡献.

若有 $2$ 个这样的段,则一共有 $4$ 个 “半段” 可以用于交换,枚举 $4$ 种交换情况,若合法,则继续 $dfs$ .

若这样的段 $>2$ 个,则一定没有贡献.

最坏情况下每次都要枚举 $4$ 种交换情况,时间复杂度 $O(4^n\cdot n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=(1<<12)+10,K=12+1;
ll fac[K],pw[K],ans=0;
int n,a[MAXN];
bool invalid(int p,int k)
{
	for(int i=1;i<pw[k];++i)
		if(a[p+i]!=a[p+i-1]+1)
			return true;
	return false;
}
void swap_part(int x,int y,int k)
{
	for(int i=0;i<pw[k];++i)
		swap(a[x+i],a[y+i]);
}
void dfs(int k,int cnt)
{
	if(k>n)
		return (void)(ans+=fac[cnt]);
	int t1=0,t2=0; // invalid parts
	for(int i=1;i<=pw[n];i+=pw[k])
		if(invalid(i,k))
		{
			if(!t1)
				t1=i;
			else if(!t2)
				t2=i;
			else // more than 2 invalid parts
				return;	
		}
	if(!t1) // 0 invalid part
		dfs(k+1,cnt);
	else if(!t2)// 1 invalid part
	{
		swap_part(t1,t1+pw[k-1],k-1);
		if(!invalid(t1,k))
			dfs(k+1,cnt+1);
		swap_part(t1,t1+pw[k-1],k-1);
	}
	else // 2 invalid parts
	{
		for(int a=0;a<2;++a)
			for(int b=0;b<2;++b)
			{
				swap_part(t1+a*pw[k-1],t2+b*pw[k-1],k-1);
				if(!invalid(t1,k) && !invalid(t2,k))
					dfs(k+1,cnt+1);
				swap_part(t1+a*pw[k-1],t2+b*pw[k-1],k-1);
			}
	}
}
int main()
{
	n=read();
	fac[0]=pw[0]=1;
	for(int i=1;i<=n;++i)
	{
		fac[i]=fac[i-1]*i;
		pw[i]=pw[i-1]*2;
	}
	for(int i=1;i<=(1<<n);++i)
		a[i]=read();
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}