状态压缩和状压DP

问题：n*n的棋盘放置n个点，保证每一行，每一列都有且只有一个点，有几种放置方式？

一、组合数解法：
ans=n!
二、状态压缩DP：

方案数目：f[0]=1,其他初始化为0

状态：10010=>2¹⁺²4=2+16=18->一个整数表示一种状态->
拆解整数->表示了所有的部件的当前状态

遍历顺序（第一层）：s:1 -> (1<<n-1)=>(111..11(n个位))
(第二层):i:1->n(枚举所有的部件)

已知当前的状态是s：

操作一：s&(1<<(n-1))

if(s&(1<<(n-1)))
{
操作二：s^(1<<(n-1))，这是根据s,找到的上一个的所有的状态
令tmp=s^(1<<(n-1))
f[s]+=f[tmp]//累加得出答案
}

神犇博客：
https://blog.csdn.net/soundwave_/article/details/52100038
（这里只讲我的具体理解）

具体代码：

#include <iostream>
#include <stdio.h>
using namespace std;
 int f[1<<21];
int main()
{
    int n, temp;
    int s, i;
    scanf("%d", &n);
    memset(f,0,sizeof(f));
    f[0] = 1;//边界条件
    for(s = 1; s <= (1<<n)-1; s++)
    { 
        for(i = 1; i <= n; i++)
            if(s & (1<<(i-1)))//排除掉第i行所有不能放置的位置之后的可放位置
            {
                temp = s ^ (1<<(i-1));//可以得到s状态的状态
                f[s] += f[temp];//s状态下的方案数
            }
    }
    printf("%d", f[(1<<n)-1]);
    return 0;
}