ZJ k914 - 肯肯肯的正方形

<<回主頁

題目大意

給你

$N$ 個長得有點特別的正方形(左上和右下的點之間有邊)，把他們連起來所形成的圖形，有幾種 從紅點到藍點 一筆畫的方法 ?

Subtask 1 :

$N\le 5$

這個子任務簡單而暴力，題目既然是個圖，你當然可以把他當成圖論的問題，把圖建出來，你就可以把他當成是一個圖 (廢話)，你只要暴力 DFS 所有可能其實就可以，時間複雜度為某種指數形式的醜東西。然後你可以考慮本機建表。 寫出來你的程式大概會長這樣。

C++ code by kenkenken:

#include <bits/stdc++.h>
using namespace std;

int n, cnt, ans;
vector<vector<pair<int, int>>> adj;
// cnt = 4 * n + 1
vector<map<int , int>> dp;

int dfs(int x, int mask) {
    if (dp[x].count(mask)) return dp[x][mask];
    if (__builtin_popcount(mask) == cnt) return 1;
    int res = 0;
    for (auto [i, id] : adj[x]) {
        if (!(mask >> id & 1)) {
            res += dfs(i, (mask | 1 << id));
        }
    }
    return dp[x][mask] = res;
}

void add_edge(int u, int v) {
    adj[u].push_back({v, cnt});
    adj[v].push_back({u, cnt++});
}

signed main() {
    cin >> n;
    adj.assign(2 * n + 2, vector<pair<int, int>>(0));
    dp.resize(2 * n + 2);
    for (int i = 0; i + 1 < 2 * n + 2; i += 2) {
        add_edge(i, i + 1);
    }
    for (int i = 0; i + 2 < 2 * n + 2; i++) {
        add_edge(i, i + 2);
    }
    for (int i = 0; i + 3 < 2 * n + 2; i += 2) {
        add_edge(i, i + 3);
    }
    assert(cnt == 4 * n + 1);
    cout << dfs(0, 0) << '\n';
}

Subtask 2 :

$N\le 100$

如果你直接提交上面的程式，你會發現數字一大，可能

$N=10$ 之類的就會跑不動，所以代表要找看看比較快的方法，你可能可以使用某種怪怪的

$\text{DP}$，但我也不知道，然後他的複雜度可能是

$O(N^2)$ 到

$O(N^4)$ 之類的，我一開始的想法是

$O(N^2)$ 低批，然後後來發現他是錯的，不過這就留給讀者想看看當回家作業。

$O(N)$ 的作法

雖然題目最後一個子任務給的是到

$N={10}^{18}$，但我們先想想

$O(N)$ 的作法.jpg ，我們先定義

$A_i$ 代表對於本問題

$N=i$ 時的答案。 (當然我們不知道

$N$ 很大時他是多少)，另外我們再定義另一個問題 :

這個是把最左邊直的那條擦掉，然後我們定義

$B_i$ 為上圖從綠點走到藍點一筆畫的方法數，雖然這問題感覺很多餘。

接著我們先回到原本的問題 ㄟ等等那你生另個問題出來幹嘛阿
原本的問題，起始的第一步可以分成三種狀況 (恩有三條路聽起來很合理 R )

Case A-1 :

往下走的，咦? 這不就是

$B_i$ 嗎? 雖然我也還不知道

$B_i$ 怎麼求，不過等等再說。

Case A-2 :

好像看不出甚麼ㄟ? 不然再討論深一點 ?

Case A-2-1 :

你會發現他接著只能往上、往右，然後又變成跟原題的形狀一樣了 ! 所以其實他是

$A_{i-1}$ 啦。

Case A-2-2 :

這需要一點想像力，可以看左下醜醜的圖，你會發現他其實是

$A_{i-1}$。

Case A-2-3 :

這更需要想像力了，他其實就是

$B_{i-1}$ 但左上角多個環，但其實你可以想像成 : 經過左上角的那點，然後選環的一邊進去繞一圈，也就是有兩個選擇，所以結論他是

$2\times B_{i-1}$。

Case A-3:

這是最後一個 case，用剛剛 case A-2-3 的神奇想法，很快看的出來他是

$2\times A_{i-1}$。

那我還是不知道

$B$ 怎麼求阿 zzzzz ，也許你會這麼想。

$B$ 其實同樣可以分 case 做 :

Case B-1:

這應該很明顯看的出來他是

$A_{i-1}$。

Case B-2:

沿用上次的想像力，看的出來他是

$A_{i-1}$。

Case B-3:

繼續沿用上次的想像力，看的出來他是

$2\times B_{i-1}$。

最後經由整理，你應該可以得到下方的轉移式:

$A_i=B_i+2B_{i-1}+4A_{i-1}$

$B_i=2B_{i-1}+2A_{i-1}$

有了這東西其實只要知道

$A_1$ 、

$B_1$ 就可以在

$O(N)$ 內求出

$A_n$ 了 !

Subtask 3 :

$N\le {10}^{18}$

我們發現

$O(N)$ 還是不夠快。

我們可以再整理一下把上面的

$A_i$ 算式內的

$B_i$ 代換，然後發現他其實可以矩陣快速冪。

最後整個問題其實可在

$O(logN)$ 解決 !!