題面

在 n * n ( n <= 20 )?的方格棋盤(pán)上放置n?個(gè)車(chē)，某些格子不能放，求使它們不能互相攻擊的方案總數(shù)。

注意：同一行或同一列只能有一個(gè)車(chē)，否則會(huì)相互攻擊

輸入格式

輸入文件第一行，有兩個(gè)數(shù)n, m ,n表示方格棋盤(pán)大小,m表示不能放的格子數(shù)量

下面有m行,每行兩個(gè)整數(shù),為不能放的格子的位置。

輸出格式

輸出文件也只有一行，即得出的方案總數(shù)。

樣例

樣例輸入

2 1
1 1

樣例輸出

1

?

分析

一如既往的，狀態(tài)壓縮動(dòng)態(tài)規(guī)劃。

限制分為兩部分：棋盤(pán)本身的限制 ， ”車(chē)（ju）“自身的限制。

?

我們使用a數(shù)組記錄棋盤(pán)本身的限制即可，a [ x ]表示第x行限制情況所對(duì)應(yīng)的十進(jìn)制數(shù)字。?

?

這道題的有一個(gè)有意思的地方：一行里只能有一個(gè)車(chē)，一列里只能有一個(gè)車(chē)。

一行里只能有一個(gè)車(chē)，意思就是，我們可以只用一個(gè)二進(jìn)制串s，就可以表示之前所有行（包括目前行）一共放置的車(chē)的狀態(tài)了！

同時(shí)，這個(gè)限制串中"1"的個(gè)數(shù)，就是我們目前所在的行號(hào)！

特別注意，這個(gè)s串中，包括目前行的那個(gè)“1”！

?

比如我們有限制串：01101

那么我們目前處在第三行。那么我們具有如下的情況：

目前第三行的狀態(tài)為：01000（即我在2號(hào)上放了一個(gè)車(chē)），則前兩行的合狀態(tài)為00101（前兩行里分別在3號(hào)和5號(hào)位置上放了車(chē)）

目前第三行的狀態(tài)為：00100（即我在3號(hào)上放了一個(gè)車(chē)），則前兩行的合狀態(tài)為01001（前兩行里分別在2號(hào)和5號(hào)位置上放了車(chē)）

目前第三行的狀態(tài)為：00001（即我在5號(hào)上放了一個(gè)車(chē)），則前兩行的合狀態(tài)為01100（前兩行里分別在2號(hào)和3號(hào)位置上放了車(chē)）

則我們定義f [ s ]為：在s串的狀態(tài)下，一共可能的放置方案數(shù)目。

注意，s本身就攜帶著“階段（行號(hào)）”和“狀態(tài)”兩層信息，所以動(dòng)規(guī)數(shù)組 f 只用一維就可以了。

?我們?cè)儆肵i表示以前行的所有可能的合狀態(tài)（就是例子里我標(biāo)藍(lán)的部分，X1,X2,X3）

則有 f [ s ] = f [ X1 ] f [ X2 ] f [ X3 ] …… f [ Xi ]

?

那么如何實(shí)現(xiàn)是一個(gè)問(wèn)題。我們有這個(gè)函數(shù)：lowbit ( x )

如果不知道的話，可以百度。我在這里簡(jiǎn)單說(shuō)幾句

lowbit ( x ) 返回的是一個(gè)數(shù)x（二進(jìn)制形式）中，最低位的1，與其后的所有0，組成的的數(shù)值。

舉例一：100001110100111000

　　該數(shù)字的lowbit值為“1000”，即8

舉例二：10001010

　　該數(shù)字的lowbit值為“10”，即2

舉例三：1001

　　該數(shù)字的lowbit值為“1”，即1

實(shí)現(xiàn)方式

?

int lowbit(int x){return (x&(-x));}

為什么這么做可以？利用了負(fù)數(shù)使用補(bǔ)碼儲(chǔ)存的原理。具體的自己去百度吧。

?

使用lowbit函數(shù)，我們就可以使用這樣的方式來(lái)統(tǒng)計(jì)，s數(shù)串里“1”的個(gè)數(shù)，以獲取它所攜帶的行號(hào)信息：第“cnt”行

for(int i=s;i;i-=lowbit(i))cnt  ;//當(dāng)前是第cnt行

?

在執(zhí)行那個(gè)標(biāo)藍(lán)部分，和動(dòng)態(tài)轉(zhuǎn)移的時(shí)候，我們使用這樣一種巧妙的方式來(lái)進(jìn)行尋找s所有子序列的工作

for(int i=s;i;i-=lowbit(i)){
    if(!(a[cnt] & lowbit(i))){
        int x=s^lowbit(i);
        f[s] =f[x];
    }
}

我們模擬一下：假設(shè)當(dāng)前s串為“ 010110010”

那么開(kāi)始：

?

i 記錄：010110010；lowbit（i）=10，這個(gè)就是我們目前假設(shè)的本行車(chē)所在的位置。

“如果該行障礙 a [ cnt ]條件允許”，那么我們將原來(lái)s串010110010，中的“10“消去，變?yōu)?10110000，記錄為x。這個(gè)x就是之前行的合狀態(tài)。

將 f [ s ] 加上這一種之前合狀態(tài)的數(shù)目。

?

?i 減去 10，i記錄：010110000；lowbit ( i ) =10000，這個(gè)就是我們目前又假設(shè)的本行車(chē)所在位置的另一種情況。

“如果該行障礙 a [ cnt ]條件允許”，那么我們將原來(lái)s串010110010，中的“10000“消去，變?yōu)?10100010，記錄為x。這個(gè)x就是之前行的合狀態(tài)。

將 f [ s ] 加上這一種之前合狀態(tài)的數(shù)目。

?

i 減去 10000，i記錄：010100000；lowbit ( i ) =100000，這個(gè)就是我們目前又假設(shè)的本行車(chē)所在位置的另一種情況。

“如果該行障礙 a [ cnt ]條件允許”，那么我們將原來(lái)s串010110010，中的“100000“消去，變?yōu)?10010010，記錄為x。這個(gè)x就是之前行的合狀態(tài)。

將 f [ s ] 加上這一種之前合狀態(tài)的數(shù)目。

?

i 減去 100000，i記錄：010000000；lowbit ( i ) =10000000，這個(gè)就是我們目前又假設(shè)的本行車(chē)所在位置的另一種情況。

“如果該行障礙 a [ cnt ]條件允許”，那么我們將原來(lái)s串010110010，中的“10000000“消去，變?yōu)?00110010，記錄為x。這個(gè)x就是之前行的合狀態(tài)。

將 f [ s ] 加上這一種之前合狀態(tài)的數(shù)目。

?

i 減去10000000，i記錄：0循環(huán)停止。

這時(shí)候 f [ s ] 就是本s串的答案了！

?

那么再提醒一個(gè)點(diǎn)。根據(jù)我之前寫(xiě)的那個(gè)玉米田的題，我們既然有n列，那么每一行就會(huì)有2^n -1種不同的s串 。

不同的是，由于我們這回首先預(yù)處理： f [ 0 ] =1，即一個(gè)不放也是一種情況，所以這回我們s串映射的就不再是0到2^n-1了，而是1到2^n?

不過(guò)最后輸出的時(shí)候，記得輸出 f [ 2^n -1 ]

而且注意longlong的問(wèn)題。數(shù)目比較大，使用longlong。

?

代碼?

?

#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn=1<<20 1;
typedef long long ll;
ll f[maxn],a[25];//a記錄行障礙狀態(tài)
int lowbit(int x){return (x&(-x));}
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i  ){
        int x,y;scanf("%d%d",&x,&y);
        a[x] =(1<<(y-1));
    }
    f[0]=1;//一個(gè)不放也是一種方案
    int maxs=1<<n;
    for(int s=1;s<=maxs;s  ){
        int cnt=0;
        for(int i=s;i;i-=lowbit(i))cnt  ;//當(dāng)前是第cnt行
        for(int i=s;i;i-=lowbit(i)){
            if(!(a[cnt] & lowbit(i))){
                int x=s^lowbit(i);
                f[s] =f[x];
            }
        }
    }
    printf("%lld\n",f[maxs-1]);
    return 0;
}

?

祝AC

?