【SDOI2015】排序

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 1 << 13;

int n , a[N];

LL ans , fac[13];

inline bool check(int len)

{

	for(register int i = 1; i <= 1 << n - len; i++)

		if (a[(i - 1) * (1 << len) + 1] + (1 << len - 1) != a[(i - 1) * (1 << len) + 1 + (1 << len-1)])

			return false;

	return true;

}

inline void sswap(int s , int t , int len)

{

	for(register int i = 0; i < len; i++)

		swap(a[s + i] , a[t + i]);

}

inline void dfs(int len , int step)

{

	if (len && !check(len)) return;

	if (len == n)

	{

		ans += fac[step];

		return;

	}

	dfs(len + 1 , step);

	int tot = 0 , c[5];

	for(register int i = 1; i <= 1 << n - len; i += 2)

	if (a[(i - 1) * (1 << len) + 1] + (1 << len) != a[i * (1 << len) + 1])

	{

		if (tot >= 4) return;

		c[++tot] = i , c[++tot] = i + 1;

	}

	if (!tot) return;

	for(register int i = 1; i <= tot; i++)

		for(register int j = i + 1; j <= tot; j++)

		{

			sswap((c[i] - 1) * (1 << len) + 1 , (c[j] - 1) * (1 << len) + 1 , 1 << len);

			dfs(len + 1 , step + 1);

			sswap((c[i] - 1) * (1 << len) + 1 , (c[j] - 1) * (1 << len) + 1 , 1 << len);

		}

}

int main()

{

	scanf("%d" , &n);

	for(register int i = 1; i <= (1 << n); i++) scanf("%d" , &a[i]);

	fac[0] = 1;

	for(register int i = 1; i <= n; i++) fac[i] = fac[i - 1] * 1LL * i;

	dfs(0 , 0);

	printf("%lld" , ans);

}
巴特西

【SDOI2015】排序

最新文章

热门文章
