方格棋盘

题目描述

在n*n(n≤20)的方格棋盘上放置n个车，每个车可以攻击到所在行和列任意一个格，求使它们不能互相攻击的方案总数。

输入格式

一个数 n

输出格式

方案总数

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

int n,m;
__int128 dp[1 << 21];

void print(__int128 x){
	if(x < 0 ) putchar('-'), x*=-1;
	if(x > 9 ) print( x / 10 );
	putchar( x % 10 + '0' );
	return;
}

int main()
{
	scanf("%d",&n);
	
	dp[0] = 1;
	for (int i = 1; i < ( 1 << n ); ++ i) {
		for (int j = i; j > 0; j -= ( j & - j )) {
			//j&-j表示找最后的一的位数
			//而j-=j&-j表示依次次向前找 i的每个1 的位数 
			dp[i] += dp[i & ~ ( j & - j )];
			//i&~(j&-j)表示在i中 把j所表示的1的位数 上的1 变成0
		} 
	}
	print(dp[( 1 << n ) - 1]);
    //表示n位的二进制数每一位都为1的情况，即每一列都放上了车
	return 0;
}