日期：2019-06-19

晚自习

关键词：状态压缩，基础，位运算

引例

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

解析

数学解法

每一行均有且只有1个车，从上向下依次每行放置，用$i$表示行号，则第$i$行有$n+1-i$种方法放置。

故总的放置方法$ans$为：$$ans=\prod_{i=1}^{n} n+1-i=n!$$

代码如下：

#include  
using namespace std;
int main(){
    int ans=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        ans*=i;
    }
    cout<

状态压缩递推解法

一个int表示一种搜索状态。

每一行均有且只有1个车，故第$i$行是否已经放置车可以用这个状态所对应的这个int的二进制码的从左向右第i位表示。

故本质是求$$f_x = \sum_{i=1}^n {f_{s-2^i}}$$

其中$f_0=1$

代码如下：

#include  
using namespace std;
int f[10485796]={0},n;
int main(){
    cin>>n;
    f[0]=1;
    for(int i=1;i<1<0;j-=(j&-j)){
            f[i]+=f[i^(j&-j)];
        }
    }
    cout<