## ZJ k914 - 肯肯肯的正方形

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 題目大意

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

### Subtask 1 : $N \leq 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 \leq 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 + 2 B_{i-1} + 4 A_{i-1}$ ||
|| $B_i = 2 B_{i-1} + 2 A_{i-1}$ ||

有了這東西其實只要知道 $A_1$ 、 $B_1$ 就可以在 $O(N)$ 內求出 $A_n$ 了 !

### Subtask 3 : $N \leq 10^{18}$

我們發現 $O(N)$ 還是不夠快。

我們可以再整理一下把上面的 $A_i$ 算式內的 $B_i$ 代換，然後發現他其實可以||矩陣快速冪||。

最後整個問題其實可在 ||$O(logN)$|| 解決 !!