[COGS 1516] 棋盘上的车

题目描述

原题地址：COGS

思路一

乘法原理水过，计算$n!$即可，复杂度$O(n)$

思路二

DP方程

每次放置一枚棋子，一行一行放，可以用一个二进制数表示状态，如$(0010011)_2$表示第一、二、五列已放棋子。

设$f(n)$是放置$n$枚棋子的方案数，可以知道，$f((0010011)_2)=f((0000011)_2)+f((0010001)_2)+f((0010010)_2)$，类似地，我们可以推出方程：

$$ \begin{cases} f(n)=0&n=0
f(n)=\sum_{i\subset n}f(i)&n\not=0 \end{cases} $$ 注意，此处的$i\subset n$的表示是不严谨的。

代码

#include <bits/stdc++.h>
using namespace std;
long long f[1 << 21];
int n;
int main()
{
    freopen("rook.in", "r", stdin);
    freopen("rook.out", "w", stdout);
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= (1 << n); ++i)  // 枚举所有状态
    {
        for (int j = 0; j < n; ++j)      // 枚举所有列
            if (i & (1 << j))            // 当该列为1
                f[i] += f[i - (1 << j)]; // (1 << j) 是一个只有一个1的二进制数，i - (1 << j) 是比i的二进制表示正好少一个1的数
    }
    cout << f[(1 << n) - 1] << endl;
}

[COGS 654] 特殊方格棋盘

题目描述

原题地址：COGS

思路

此题我不会用数学方法，只能状压DP。

DP方程不变，原理类似，只是多了一些不能放的位置。

使用一个数组a来记录不能放的位置。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll f[1 << 21];
ll a[21], ans[1 << 21];
inline int lowbit(int k) { return k & -k; }
int main()
{
    freopen("examone.in", "r", stdin);
    freopen("examone.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[x] |= (1 << (y - 1));            // 将a[x]的值设置为(1 << (y - 1))
    }
    ans[0] = 1;
    for (int i = 1; i <= (1 << n) - 1; ++i)
    {
        int l = 0, d = i;
        for (; d; d -= lowbit(d), ++l) ;   // 此处使用lowbit以确定当前已经放了几个棋子，l为已放的棋子数
        ll st = i & (~a[l]);               // 如果此处已经被钦定，则st = 0，否则st = i。
        for (int j = st; j; j -= lowbit(j))// 遍历i的所有“子集”
            ans[i] += ans[i & ~lowbit(j)]; // MAGIC!:i & ~lowbit(j)与i相比刚好少了一个1
    }
    cout << ans[(1 << n) - 1] << endl;
}

也可以这样写，风格与第一题类似：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll ans[1 << 21];
int a[21];
int lowbit(int k) { return k & -k; }
int main()
{
    freopen("examone.in", "r", stdin);
    freopen("examone.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[x] |= (1 << (y - 1));
    }
    ans[0] = 1;
    for (int i = 1; i <= (1 << n); ++i)
    {
        int l = 0, d = i;
        for (; d; d -= lowbit(d), ++l) ;
        for (int j = 0; j < n; ++j)
            if (i & (1 << j) && !((1 << j) & a[l])) // 如果当前位置不与障碍冲突，且在i中存在
                ans[i] += ans[i - (1 << j)];        // 转移
    }
    cout << ans[(1 << n) - 1] << endl;
}

参考资料

• 《状态压缩》周伟。百度文库

• 《浅谈二进制拆分》WCG。Blog

最后感谢mk的讲解