题目描述
在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;
}