记录编号	558683	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1516.棋盘上的車	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.038 s
提交时间	2021-01-17 21:41:30	内存使用	171.28 MiB

//我错了，再也不水题了 
//很显然，每一行必须放一个
//所以这题就是枚举1....n的全排列个数                           
//甚至可以用乘法原理直接做。。。。。 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list> 
using namespace std;
int n;
int k; 
const int maxn = 21;
list<int> s[maxn];
list<int>::iterator it;
unsigned long long f[maxn][1 << 20];
int lowbit(int x) {
	return x & (~ x + 1);
}
int uppernum(int x) {
	int cnt = 0;
	while(x) {
		x -= lowbit(x);
		++ cnt;
	}
	return cnt;
}
void DP() {
	for(int i = 1;i < (1 << n);++ i) {
		s[uppernum(i)].push_back(i);
	}
	return ;
}
int main() {
	freopen("rook.in","r",stdin);
	freopen("rook.out","w",stdout);
	scanf("%d",&n);
	int MAX = (1 << n) - 1;
	memset(f , 0 , sizeof(f));
	for(int k = 1;k < (1 << n);k <<= 1)f[1][k] = 1;
	DP();
	for(int i = 2;i <= n;++ i) {
		for(it = s[i - 1].begin();it != s[i - 1].end();++ it) {
			int x = *it;
			int pos = (~ x) & MAX;
			while(pos) {
				int lw = lowbit(pos);
				pos -= lw;
				f[i][lw | x] += f[i - 1][x];
			}
		}
	}
	printf("%llu",f[n][(1 << n) - 1]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}