记录编号	24190	评测结果	AAAAA
题目名称	[HAOI 2004模拟]数列问题	最终得分	100
用户昵称	Oo湼鞶oO	是否通过	通过
代码语言	C++	运行时间	0.066 s
提交时间	2011-03-29 20:24:59	内存使用	0.27 MiB

#include <fstream>
#include <cmath>

#define I_F "dfs3.in"
#define O_F "dfs3.out"
#define MAXn 15

using namespace std;

struct edges
{
	short x,y;
};

short s[MAXn];
short primes[MAXn*2]={2};
edges map[MAXn*MAXn*2];
short head[MAXn+2];
short n,pn=1;
bool f[MAXn];
long ans;

ofstream fout(O_F);

void Input();
bool Prm(short);
void GetPrimes();
void GetMap();
void Output();
void Dfs(short);

int main()
{
	Input();
	GetPrimes();
	GetMap();
	Dfs(0);
	fout<<ans<<'\n';
	fout.close();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n;
	fin.close();
}

bool Prm(short x)
{
	for (short i=0; (i<pn)&&(primes[i]<=sqrt((double)x)); i++)
		if (x%primes[i]==0)
			return false;
	return true;
}

void GetPrimes()
{
	for (short i=3; i<=n*2; i+=2)
		if (Prm(i))
			primes[pn++]=i;
}

void GetMap()
{
	short m=0;
	#define P primes[j]-i
	for (short i=1; i<=n; i++)
	{
		head[i]=m;
		for (short j=0; j<pn; j++)
			if ((P>0)&&(P<=n))
			{
				map[m].x=i;
				map[m++].y=P;
			}
	}
	head[n+1]=m;
}

void Output()
{
	ans++;
	for (short i=0; i<n-1; fout<<s[i++]<<' ');
	fout<<s[n-1]<<'\n';
}

void Dfs(short x)
{
	if (x>=n)
		Output();
	else 
		if (x==0)
			for (short i=1; i<=n; f[i++]=false)
			{
				f[i]=true;
				s[x]=i;
				Dfs(1);
			}
		else
			for (short i=head[s[x-1]]; i<head[s[x-1]+1]; i++)
				if (!f[map[i].y])
				{
					f[map[i].y]=true;
					s[x]=map[i].y;
					Dfs(x+1);
					f[map[i].y]=false;
				}
}