Description

 小A有一個1-2^N的排列A[1..2^N],他希望將A數組從小到大排序,小A可以執行的操作有N種,每種操作最多可以執行一次,對于所有的i(1<=i<=N),第i中操作為將序列從左到右劃分為2^{N-i+1}段,每段恰好包括2^{i-1}個數,然后整體交換其中兩段.小A想知道可以將數組A從小到大排序的不同的操作序列有多少個,小A認為兩個操作序列不同,當且僅當操作個數不同,或者至少一個操作不同(種類不同或者操作位置不同).

Input

第一行,一個整數N

Output

一個整數表示答案

Sample Input

Sample Output

HINT

100%的數據, 1<=N<=12.

Source

Round 1 感謝ZKY制作非官方數據

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

dfs+神奇的思路~

orzPoPoQQQ，orz黃學長……

思路詳見黃學長的博客：http://hzwer.com/6839.html~

#include<cstdio>#include<iostream>using namespace std;int n,a[5005],fac[13],bin[20];long long ans;bool che(int u,int v){	for(int i=1;i<v;i++) if(a[i+u]!=a[i+u-1]+1) return 0;	return 1;}void swapp(int u,int v,int k){	for(int i=0;i<bin[k];i++) swap(a[u+i],a[v+i]);}void dfs(int u,int v){	if(u==n+1)	{		ans+=fac[v];return;	}	int k1=0,k2=0;	for(int i=1;i<=bin[n];i+=bin[u])	  if(!che(i,bin[u]))	  {	  	if(!k1) k1=i;	  	else if(!k2) k2=i;	  	else return;	  }	if(!k1 && !k2) dfs(u+1,v);	else if(!k2)	{		swapp(k1,k1+bin[u-1],u-1);dfs(u+1,v+1);swapp(k1,k1+bin[u-1],u-1);	}	else	{		for(int x=0;x<=1;x++)		  for(int y=0;y<=1;y++)		  {		  	swapp(k1+x*bin[u-1],k2+y*bin[u-1],u-1);		  	if(che(k1,bin[u]) && che(k2,bin[u]))		  	{		  		dfs(u+1,v+1);		  		swapp(k1+x*bin[u-1],k2+y*bin[u-1],u-1);		  		break;			}			swapp(k1+x*bin[u-1],k2+y*bin[u-1],u-1);		  }	}}int main(){	fac[0]=bin[0]=1;	for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;	for(int i=1;i<=12;i++) fac[i]=fac[i-1]*i;	scanf("%d",&n);	for(int i=1;i<=bin[n];i++) scanf("%d",&a[i]);	dfs(1,0);	PRintf("%lld/n",ans);	return 0;}