藍橋杯 回路計算（狀壓DP）

藍橋杯 回路計算（狀壓DP）

• 問題網址https://www.lanqiao.cn/problems/1462/learning/?contest_id=73

• 不了解狀壓DP是什麼的小夥伴可以先去B站看看這個視訊

  https://www.bilibili.com/video/BV1Z4411x7Kw/?spm_id_from=333.337.search-card.all.click

• 樓棟是從0開始編号的。

• 先講一個最簡單的例子：二維數組F [i] [j]，i 可以看做二進制，表示狀态，而 j 表示 i 狀态下的一種情況。

  假設有5個點，i表示01101，經過了點3、2、0的一種狀态，但是順序是咋樣的呢，現在停留在哪個點呢？不知道。那我們再來看j，假設j=2，說明目前停留在2這個點上，而F[13][2]=2，表示什麼？就表示01101路徑狀态下，最後到達點2的情況有2種，不管起點是啥，情況就是2種。這樣更不可能存在重複的情況，為什麼呢？因為雖然都經過了3、2、0但是它們最終的落腳點不一樣，排列的問題，是以肯定不存在重複。

• 接着我們再來講一講狀态轉移方程的問題。首先要明白一個問題，i狀态是遞增的，每次新的i的狀态的各個情況都是未知的，都是新的狀态，需要根據先前的狀态來推敲出來。假設i=01101，那我們是不是要求它的各種落腳點情況？答案是顯然的。也就是要求F[01101][01000]、F[01101][00100]、F[01101][00001]三個值的大小。（注意實際代碼中存的都是10進制，從左到右為F[13][3]、F[13][2]、F[13][0]，這邊寫成二進制好了解一些）《這三個值肯定先前不知道，因為i狀态是新的》。怎麼求呢？那肯定是利用先前的狀态。比如既然要知道求F[01101][01000]這個，是不是可以求F[00101]這個狀态下各種情況F[00101][00100]、F[00101][00001]這兩種情況的落腳點是否能到點01000，一旦能到達是不是就狀态就從00101變成了01101了？而且能到達的情況數不就等于F[00101][00001]，也就是落腳點00001與01000存在邊或者00100與01000存在邊嘛。
• 總結一下就是來了一個新狀态i，得到這個狀态i各個可能落腳點的情況，然後就要求逐個分析各個落腳點情況的總數了，确定好一個落腳點j，把i狀态中的這個落腳點j去除得到狀态(i-j)，這個狀态中也有多個落腳點情況，隻要多個落腳點中與j有邊，那是不是狀态i落腳點j的情況數是不是就等于狀态(i-j) 落腳點x(與j有邊) 的情況總數和。

直接看代碼吧，講的有點繞，大家可以先去B站看看有關狀壓DP的講解，再結合代碼看這道題。注釋我盡量寫的詳細了一點。一起加油。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 21;

int n = 21;
LL ans;
// 存儲兩棟樓是否有通道的數組。
int st[N][N];
// 0到21個點全1，總共有2^21次方個數，1左移21位就等于2^21次方，剛剛好。
LL f[1 << N][N];

int gcd(int x, int y)
{
    if (x % y == 0)
    {
        return y;
    }
    int res = gcd(y, x % y);
    return res;
}

int main()
{
    // 找到各個樓棟之間的通道
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (gcd(j + 1, i + 1) == 1)
            {
                st[i][j] = st[j][i] = 1;
            }
        }
        // 同樓層之間通道設為0，其實這個也用不到，下面代碼不會判斷自己到自己是否存在邊。
        st[i][i] = 0;
    }

    // 狀态1（表示經過了0号樓）落腳點為0，認為是有一種情況，不然全為0，DP怎麼弄都是0。
    f[1][0] = 1;

    // 0到21個點全1，總共有2^21次方個數，1左移21位就等于2^21次方，剛剛好。
    for (int i = 0; i < (1 << N); i++)
        // i通路狀态下。找它的各個落腳點j情況。
        for (int j = 0; j < N; j++)
        {   
            // 既然是狀态i的落腳點，那肯定得在i裡面有出現，是以i右移j位為1與上1為1說明存在。
            // 那麼經過狀态 i 到達 j 的方案數等于從起點不經過點 j（也就是狀态i中沒有j） 到達全部與 j 點可達的點 k 方案數
            if (i >> j & 1)
            {
                // 找到了其中一個落腳點j，那我就從i裡面把落腳點j删去，從删去後的狀态(假設狀态為i-j)找這個狀态是否有落腳點與j相連。
                for (int k = 0; k < N; k++)
                { 
                    // 假設從i删去落腳點j，那麼就不會再找j這個點（前面st[j][j]=0)，這種情況直接pass了。
                    // 那就從删去的狀态i-j中找這個狀态的所有落腳點(隻有 i >> k & 1 = 1 才是落腳點) 是否與j有邊。
                    // 有邊就好辦了，直接i-j狀态有邊的落腳點k這個情況總數  先加到 i狀态落腳點j這個情況裡面
                    // 再找其他的i-j狀态下與j有邊的落腳點。
                    if (i >> k & 1 && st[j][k])
                    {   
                        // 所有這邊為加，因為i-j狀态下與j有邊的落腳點可能不止一個
                        // i - (1 << j)  表示的就是從i裡面把落腳點j删去,也就是狀态i-j，再在這個狀态找到落腳點k與j有邊，那就直接加進去。
                        f[i][j] += f[i - (1 << j)][k];
                    }
                }
            }
        }

    // 因為每個點都能通向0号大樓（從0開始）
    // 那麼我們可以認為全部點都經過了，也就是21個位置全為1，就等于(1<<N)-1，這個情況的每個落腳點總計20個落腳點，除了0号樓本身，
    // 代表的意思就是從任意點走完全部21個點到達這20落腳點的總數和就等于回路的總數，因為每個點都能通向0号大樓（從0開始）。
    for (int i = 1; i < N;i++)
        ans += f[(1 << N) - 1][i];

    // 有一個有意思的情況，為什麼不直接輸出f[(1<<N)-1][0]呢？因為它的起始點是0，不能自己又走到0，DP求得是非回路的。
    // 正因為起始點是1，那麼必須會經過1，所有不經過1的狀态，那麼它的各種情況都是0，這與初值的設定有關。

    cout << f[5][0] << f[14][2] << f[14][14] << endl;

    cout << ans << endl;
    // cout << f[(1 << N) - 1][0] << endl;
    return 0;
}