1516. 棋盘上的车[组合数学][状态压缩]

1516. 棋盘上的车

☆   输入文件：rook.in   输出文件：rook.out   简单对比
时间限制：1 s   内存限制：256 MB

【题目描述】

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

【输入格式】

一行一个正整数n。

【输出格式】

一行一个正整数，即方案总数。

【样例输入】

3

【样例输出】

6

【来源】

周伟，《状态压缩》，引例

 

/*
乘法原理:
第一步有n种决策，第二步有 n-1种决策，…… 第N步有 1种决策
前一步都对后一步产生影响。都对答案有贡献。
因此，ans=n! 
*/
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll n,ans=1;
int main(){
    freopen("rook.in","r",stdin);
    freopen("rook.out","w",stdout);
    cin>>n;
    for(ll i=1;i<=n;i++) ans*=i;
    cout<<ans; 
}

//f[11111]表示在五行每一行都放车的方案数 
#include<cstdio>
typedef long long ll;
ll n,f[1<<20];
int main(){
    freopen("rook.in","r",stdin);
    freopen("rook.out","w",stdout);
    scanf("%lld",&n);
    f[0]=1;
    for(ll  i=1;i<(1<<n);i++){
        for(ll S=i;S;S-=(S&-S)){
            f[i]+=f[i& ~(S&-S)];
        }
    }
    printf("%lld
",f[(1<<n)-1]);
    return 0;
}