# 111學年度上學期進階班期末考題解

## 哥德巴赫猜想(偽)

`tag: prime number, 梗題`

給你一數$N$
把$N$拆成多個質數相加

---

不知道哪個時候想到的題目
反正當時想到就想出成梗題

---

### $1\%:\ N \in prime\ number$

既然$N$自己就是質數
那就輸出他就好了

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        cout << N << endl << 1 << endl;
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(1)$

---

### $14\%:\ 1 < N \leq 20$

可以直接把 $2 \sim 20$ 的答案列出來

| $N$ | $ans$ | $N$ | $ans$ |
| ---- | ------ | ---- | ------ |
| $2$ | $2*1$ | $12$ | $2*6$ |
| $3$ | $3*1$ | $13$ | $13*1$ |
| $4$ | $2*2$ | $14$ | $2*7$ |
| $5$ | $5*1$ | $15$ | $3*5$ |
| $6$ | $2*3$ | $16$ | $2*8$ |
| $7$ | $7*1$ | $17$ | $17*1$ |
| $8$ | $2*4$ | $18$ | $2*9$ |
| $9$ | $3*3$ | $19$ | $19*1$ |
| $10$ | $2*5$ | $20$ | $2*10$ |
| $11$ | $11*1$ | | |

然後套一堆`if`就可以了

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        if(N == 2) {
            cout << 2 << endl << 1 << endl;
        }
        if(N == 3) {
            cout << 3 << endl << 1 << endl;
        }
        if(N == 4) {
            cout << 2 << endl << 2 << endl;
        }
        if(N == 5) {
            cout << 5 << endl << 1 << endl;
        }
        if(N == 6) {
            cout << 3 << endl << 2 << endl;
        }
        if(N == 7) {
            cout << 7 << endl << 1 << endl;
        }
        if(N == 8) {
            cout << 2 << endl << 4 << endl;
        }
        if(N == 9) {
            cout << 3 << endl << 3 << endl;
        }
        if(N == 10) {
            cout << 2 << endl << 5 << endl;
        }
        if(N == 11) {
            cout << 11 << endl << 1 << endl;
        }
        if(N == 12) {
            cout << 2 << endl << 6 << endl;
        }
        if(N == 13) {
            cout << 13 << endl << 1 << endl;
        }
        if(N == 14) {
            cout << 2 << endl << 7 << endl;
        }
        if(N == 15) {
            cout << 3 << endl << 5 << endl;
        }
        if(N == 16) {
            cout << 2 << endl << 8 << endl;
        }
        if(N == 17) {
            cout << 17 << endl << 1 << endl;
        }
        if(N == 18) {
            cout << 2 << endl << 9 << endl;
        }
        if(N == 19) {
            cout << 19 << endl << 1 << endl;
        }
        if(N == 20) {
            cout << 2 << endl << 10 << endl;
        }
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(1)$

---

### $20\%:\ 1 < N \leq 10^4,\ N \in even\ number$

從題目可以得知，較小的偶數可以確定符合這個猜想
所以在這個測資點，可以把$N$拆成兩個質數(除了$N=2$)

記得要特判$N=2$

而要怎麼去確定一個數字是否為質數呢

inline bool is_prime(LL n) {
    for(LL i = 2; i * i <= n; i ++ ) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

這個方法可以$O(\sqrt{n})$算出$n$是否為質數

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

inline bool is_prime(LL n) {
    for(LL i = 2; i * i <= n; i ++ ) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        if(N == 2) {
            cout << 2 << endl << 1 << endl;
            continue;
        }
        for(LL i = 2; i < N; i ++ ) {
            LL a = i, b = N - i;
            if(is_prime(a) && is_prime(b)) {
                cout << a << " " << b << endl;
                cout << 1 << " " << 1 << endl;
                break;
            }
        }
    }
}

:::

`Time Complexity:` $O(TN\sqrt{N})$
`Space Complexity:` $O(1)$

---

### $(1\%) + 14\% + 20\% + 25\% = 60\% :\ 1 < N \leq 10^4$

一個數如果不是偶數，那他就是奇數(廢話)

那我們可以把$N$分成兩種情況來看：

$N$為偶數：
直接代$20\%$的code

$N$為奇數：
那有一個$N$為奇數的話，可以寫成$3 + (N - 3)$
且$3$為質數，$N - 3$為偶數
接著就可以用$N - 3$去代$15\%$的code(除了$N=3 or N=5$)

記得$N=2\ or\ N=3\ or\ N=5$時要特判

這樣就可以同時解掉$9\%,\ 15\%$和$35\%$的側資點

照理來說$1\%$的側資點不會被解掉
只是因為我把那個側資點的$T$設有夠小($20$)
加上你只要去判他是不是質數就能拿到這$1\%$了
所以我分數就直接送下去了

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

inline bool is_prime(LL n) {
    for(LL i = 2; i * i <= n; i ++ ) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        if(N == 2) {
            cout << 2 << endl << 1 << endl;
            continue;
        }
        if(N == 3) {
            cout << 3 << endl << 1 << endl;
            continue;
        }
        if(N == 5) {
            cout << 5 << endl << 1 << endl;
            continue;
        }
        bool odd = 0;
        if(N % 2 == 1) {
            odd = 1;
            N -= 3;
        }
        for(LL i = 2; i < N; i ++ ) {
            LL a = i, b = N - i;
            if(is_prime(a) && is_prime(b)) {
                if(odd)
                    cout << 3 << " ";
                cout << a << " " << b << endl;
                if(odd)
                    cout << 1 << " ";
                cout << 1 << " " << 1 << endl;
                break;
            }
        }
    }
}

:::

`Time Complexity:` $O(TN\sqrt{N})$
`Space Complexity:` $O(1)$

---

### $1\% + 14\% + 20\% + 25\% + 40\% = 100\% :\ 1 < N \leq 2^{31} - 1$

定理：當有一個$N\ge 2$時，可以寫成$2m+3n(m, n \in \mathbb{Z^+})$

證明：

一數$N$可以被分成兩種狀態，奇數or偶數

當$N$為偶數：
$N$可以被寫成$2a$，則$m=a,\ n=0$

當$N$為奇數：
$N$可以被寫成$2a+1=2(a-1)+3$，則$m=a-1,\ n=1$

$\mathbb{Q.E.D.}$

因為$n=0$在題目的輸出中是合法的
所以也不用特判，直接輸出即可

這就是這題梗的地方
(而且程式碼有夠簡單)

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        if(N % 2) {
            cout << 2 << " " << 3 << endl;
            cout << N / 2 - 1 << " " << 1 << endl;
        }
        else {
            cout << 2 << endl;
            cout << N / 2 << endl;
        }
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(1)$

---
---

## 兩元三元

`tag: quadratic equation, 成年禮`

有兩元，有三元
一個兩元 + 一個三元 = 一個七元

給你一個數字$N$
有兩元$m$個跟三元$n$個
將這堆錢的幣值最大化
求有幾種不重複的$(m, n)$，可以得到$N$的總價錢

---

高二成年禮玩大地遊戲的時候想到的題目
想了想發現還滿水的

---

### $5\% :\ 1 \leq N \leq 10$

直接把答案列出來就可以了

| N | ans | N | ans |
| --- | --- | ---- | --- |
| $1$ | $0$ | $6$ | $2$ |
| $2$ | $1$ | $7$ | $1$ |
| $3$ | $1$ | $8$ | $1$ |
| $4$ | $1$ | $9$ | $2$ |
| $5$ | $0$ | $10$ | $2$ |

然後用陣列就可以了

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    LL arr[10] = {0, 1, 1, 1, 0, 2, 1, 1, 2, 2};
    while(T -- ) {
        LL N;
        cin >> N;
        cout << arr[N - 1] << endl;
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(N)$

---

### $5\% + 20\% = 25\% :\ 1 \leq N \leq 10^3$

可以去模擬有幾個兩元跟三元
用雙層迴圈去模擬
當還沒氧化前的總和就$>N$就可以跳下一次迴圈

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        LL ans = 0;
        for(LL i = 0; ; i ++ ) {
            if(i * 2 > N)
                break;
            for(LL j = 0; ; j ++ ) {
                if(i * 2 + j * 3 > N)
                    break;
                LL tmp = min(i, j);
                LL num = tmp * 7 + (i - tmp) * 2 + (j - tmp) * 3;
                if(num == N)
                    ans ++ ;
            }
        }
        cout << ans << endl;
    }
}

:::

`Time Complexity:` $O(TN^2)$
`Space Complexity:` $O(1)$

---

### $5\% + 20\% + 35\% = 60\% :\ 1 \leq N \leq 10^6$

題目說要將幣值最大化
也就是要將能換成七元的錢都換成七元

當我們這樣做時
我們會發現最後沒有被換成七元的一定是兩元或三元其中一種(或是都沒剩)

那這樣題目就可以另寫成：
求$N = 7m+2n\ or\ N = 7m+3n$的$(m, n)$有幾組不重複解$(m, n \in \mathbb{Z^+})$

那我們可以去對$m$做窮舉，找$n$的可能情況
但要注意一件事
當$n = 0$時，$(m, n)$會被同時算在$7m+2n\ \&\ 7m+3n$中

所以這時候的答案要$-1$
那什麼時候$n$會出現$=0$的情況呢
就是當$N = 0\ (mod\ 7)$的時候

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        LL ans = 0;
        for(LL i = N; i >= 0; i -= 7) {
            ans += (i % 2 == 0);
            ans += (i % 3 == 0);
        }
        if(N % 7 == 0)
            ans -- ;
        cout << ans << endl;
    }
}

:::

`Time Complexity:` $O(TN)$
`Space Complexity:` $O(1)$

---

### $5\% + 20\% + 35\% + 40\% = 100\% :\ 1 \leq N \leq 2^{31} - 1$

要想 <b style="color: lime;">AC</b> 就要動用到一點數學常識了

先以$7m+2n=N$為例
$7m+2n = 7(m-2)+2(n+7) = 7(m-4)+2(n+14)$
$=\cdots=7(m-2k) + 2(n+7k)\ (k \in \mathbb{Z^+})$
然後因為$(m, n \in \mathbb{Z^+})$，所以要滿足$(m-2k) \ge 0$

我們可以先找到$m$最大的解，然後找有幾組的$(m-2k) \ge 0$，也就是$m/2+1$組

先以$7m+3n=N$也是一樣的道理

然後記得當$N = 0\ (mod\ 7)$的時候要把答案$-1$

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        LL ans = 0, a, b;
        a = N / 7, b = N % 7;
        while(b % 2)
            a -- , b += 7;
        if(a >= 0)
            ans += a / 2 + 1;
        a = N / 7, b = N % 7;
        while(b % 3)
            a -- , b += 7;
        if(a >= 0)
            ans += a / 3 + 1;
        if(N % 7 == 0)
            ans -- ;
        cout << ans << endl;
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(1)$

---
---

## 數之數織

`tag: DFS, pruning`

給你一個數織，完成他

---

當初想說除了數獨跟八皇后還有什麼比較好出的DFS題
然後就想到了這個東西
去查才知道這個鬼東西叫數織

題外話
我這題想了好幾天
一直改想法，一直把題目`debuff`
生測資生到快崩潰

所以我要先在試前做一個大膽的猜測

### <font style="color: red; font-size: 50px">大膽的猜測</font>

這題應該不會有人(除了$frankie$)在競賽中<b style="color: lime;">AC</b>

然後我先猜$frankie$會<font>WA</font>至少$20$次

---

### $1\%:\ N = 1$

因為題目保證測資皆有解
所以很直觀的，直接輸出$1$就可以了

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N, lft, up;
        cin >> N >> lft >> up;
        cout << 1 << endl;
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(1)$

---

### $14\% :\ N = 2$

因為題目保證測資皆有解
那在$N=2$的情況下只會有$1$跟$2$這兩種答案
然後$ans=2$的情況也就只有$1\ 1\ 1\ 1$這種
其他都是$ans=1$

然後如果你想要那$1\%$也可以再判$N=1$

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N, a, b, c, d;
        cin >> N >> a >> b >> c >> d;
        if(a*b*c*d == 1)
            cout << 2 << endl;
        else
            cout << 1 << endl;
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(1)$

---

### $1\% + 14\% + 45\% = 60\% :\ N \leq 5$

就純$DFS$

但因為題目有限制格中只有一個數字
所以不用一格一格去塗黑
可以先由同一個方向塗$N$條黑格
然後塗完再用另一個方向去檢驗這個解法是否可行

這個實作可以用一個二維$bool$陣列來做
有塗黑就$1$，反之則$0$
然後記得把變數開在全域

喔然後格中有可能會出現$0$這個數字
為了避免重複計算答案
遇到$0$就直接跳下一條黑格來塗

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

constexpr LL maxN = 15;
LL N, ans;
LL lft[maxN], up[maxN];
bool mat[maxN][maxN];

inline void DFS(LL pos = 0) {
    if(pos == N) {
        for(LL i = 0; i < N; i ++ ) {
            LL cnt = 0, tmp = 0;
            // tmp: 0 = not yet in tile, 1 = in tile, 2 = over tile
            for(LL j = 0; j < N; j ++ ) {
                if(tmp == 0 && mat[j][i])
                    tmp ++ ;
                if(tmp == 1 && !mat[j][i])
                    tmp ++ ;
                if(mat[j][i] && tmp == 2)
                    return;
                cnt += mat[j][i];
            }
            if(cnt != up[i])
                return;
        }
        ans ++ ;
        return;
    }
    if(lft[pos] == 0) {
        DFS(pos + 1);
        return;
    }
    for(LL i = 0; i + lft[pos] - 1 < N; i ++ ) {
        for(LL j = i; j < i + lft[pos]; j ++ )
            mat[pos][j] = 1;
        DFS(pos + 1);
        for(LL j = i; j < i + lft[pos]; j ++ )
            mat[pos][j] = 0;
    }
}

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        ans = 0;
        memset(mat, 0, sizeof(mat));
        cin >> N;
        for(LL i = 0; i < N; i ++ )
            cin >> lft[i];
        for(LL i=  0; i < N; i ++ )
            cin >> up[i];
        DFS();
        cout << ans << endl;
    }
}

:::

`Time Complexity:` $O(TN^2)$
`Space Complexity:` $O(N^2)$

---

### $1\% + 14\% + 45\% + 40\% = 100\% :\ N \leq 10$

這題如果真的要優化的話
肯定有很多種方法
反正我這邊丟我的方法

跟$60\%$一樣，先對一個方向塗黑條
但跟$60\%$不一樣的地方在於
要一邊塗一邊用另一個方向去判斷解法是否可行
大概優化的想法在這邊
細節的話我也講一下好了

除了$lft$跟$up$，還要設一個檢查陣列$chk$跟一個計數陣列$arr$
其中$chk$是來表示「第$i$欄是否還可以被放置黑格」
並且其中的元素分成三種值：
$0:$都行，$1:$這欄的下一格一定要塗黑，$-1:$這欄不能再被塗黑
$chk$是來表示「第$i$欄被放了幾個黑格」
預設都為$0$

所以這題其實可以不用二為陣列去實作

接下來只要一邊塗黑條一邊去動態看這樣塗是否合法
就可以完成了
然後注意一些細節($0$的出現，有些欄沒被塗完，$DFS$回上層要把資料回歸 $\cdots$)
大概就能<b style="color: lime;">AC</b>了

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define mem(x) memset(x, 0, sizeof(x))
using namespace std;
using LL = long long;

constexpr LL maxN = 15;
LL N;
LL up[maxN], lft[maxN], arr[maxN], chk[maxN], ans = 0;
// chk[i] : 1 = put, 0 = all ok, -1 = don't put

inline void DFS(LL pos = 0) {
    if(pos == N) {
        for(LL i = 0; i < N; i ++ ) {
            if(arr[i] != up[i])
                return;
        }
        ans ++ ;
        return;
    }
    if(lft[pos] == 0) {
        for(LL i = 0; i < N; i ++ ) {
            if(chk[i] == 1)
                return;
        }
        DFS(pos + 1);
        return;
    }
    for(LL i = 0; i + lft[pos] - 1 < N; i ++ ) {
        bool bln = 1;
        for(LL j = 0; j < N; j ++ ) {
            if(i <= j && j <= i + lft[pos] - 1) {
                if(chk[j] < 0) {
                    bln = 0;
                    break;
                }
            }
            else if(chk[j] > 0) {
                bln = 0;
                break;
            }
        }
        if(!bln)
            continue;
        for(LL j = i; j < i + lft[pos]; j ++ ) {
            arr[j] ++ ;
            if(arr[j] == up[j])
                chk[j] = -1;
            else
                chk[j] = 1;
        }
        DFS(pos + 1);
        for(LL j = i; j < i + lft[pos]; j ++ ) {
            arr[j] -- ;
            if(arr[j])
                chk[j] = 1;
            else
                chk[j] = 0;
        }
    }
}

inline void init() {
    mem(up);
    mem(lft);
    mem(arr);
    mem(chk);
    ans = 0;
}

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        init();
        cin >> N;
        for(LL i = 0; i < N; i ++ )
            cin >> lft[i];
        for(LL i = 0; i < N; i ++ )
            cin >> up[i];
        DFS();
        cout << ans << endl;
    }
}

:::

`Time Complexity:` $O(TN^2)$
`Space Complexity:` $O(N)$

---
---

## 長方形分配者—小駿

`tag: recursion, DP, matrix exponentiation, 小駿`

有一個寬為$1$且長為$N$的矩形
從這個矩形的長邊其中一端，一直切下「長為整數且大於1的長方形」，而最後不剩
有多少切法

---

在寫$110$學科時想到的題目
是當時$pI$的簡化但又加強版

---

### $5\%:\ 1 \leq N \leq 5$

直接列出來

| N | ans |
| --- | --- |
| $1$ | $0$ |
| $2$ | $1$ |
| $3$ | $1$ |
| $4$ | $2$ |
| $5$ | $3$ |

然後用陣列

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    // IO;
    LL T;
    cin >> T;
    LL arr[5] = {0, 1, 1, 2, 3};
    while(T -- ) {
        LL N;
        cin >> N;
        cout << arr[N - 1] << endl;
    }
}

:::

`Time Complexity:` $O(T)$
`Space Complexity:` $O(N)$

---

### $5\% + 20\% = 25\%:\ 1 \leq N \leq 30$

直接用遞迴模擬切掉的長度
當完整切完就可以回傳$1$
(你要用`if else`我也是沒差啦)

然後$N=1$要特判

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

inline LL ans(LL n) {
    if(n == 0)
        return 1;
    LL r = 0;
    for(LL i = 2; i <= n; i ++ )
        r += ans(n - i);
    return r;
}

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        if(N == 1) {
            cout << 0 << endl;
            continue;
        }
        cout << ans(N) << endl;
    }
}

:::

`Time Complexity:` $O(T*2^N)$
`Space Complexity:` $O(1)$

---

### $5\% + 20\% + 30\% = 55\%:\ 1 \leq N \leq 10^3$

剛剛的`code`可以寫出以下遞迴式：

$\large{f(n) = \begin{cases} 1 \qquad \qquad \qquad \qquad if\ \ n=0 \\ 0 \qquad \qquad \qquad \qquad if\ \ n=1 \\ \Sigma_{k = 2}^{n} f(n-k)\qquad else \\ \end{cases}}$

因為我們可以從一端切下長度為$2 \sim N$的長方形

那這樣我們就可以用陣列存取重複的值
也就是用$DP$

然後從這個側資點開始
答案會超過`long long`範圍
所以別忘了$mod\ 10^9+7$

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

constexpr LL mod = 1e9 + 7;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        LL arr[N + 1];
        memset(arr, 0, sizeof(arr));
        arr[0] = 1;
        for(LL i = 1; i <= N; i ++ ) {
            for(LL j = 2; j <= i; j ++ ) {
                arr[i] = (arr[i] + arr[i - j]) % mod;
            }
        }
        cout << arr[N] << endl;
    }
}

:::

`Time Complexity:` $O(T*N^2)$
`Space Complexity:` $O(N)$

---

### $5\% + 20\% + 30\% + 35\% = 90\%:\ 1 \leq N \leq 10^6$

我們再看一下剛剛的遞迴式：

$\large{f(n) = \begin{cases} 1 \qquad \qquad \qquad \qquad if\ \ n=0 \\ 0 \qquad \qquad \qquad \qquad if\ \ n=1 \\ \Sigma_{k = 2}^{n} f(n-k)\qquad else \\ \end{cases}}$

其中我們看到`else`那邊

$\large{f(n) = \Sigma_{k = 2}^{n} f(n-k)}$

我們做一個神奇的操作，先列下這兩條式子

$f(n) \quad\;\;\, = f(n-2)+f(n-3)+f(n-4)+\cdots+f(2)+f(1)+f(0)$
$f(n-1) = \qquad\qquad\;\;\; f(n-3)+f(n-4)+\cdots+f(2)+f(1)+f(0)$

我把兩式相減得

$f(n) - f(n - 1) = f(n - 2)$

再移個項

$f(n) = f(n - 1) + f(n - 2)$

太神奇了，這不就是費氏數列嗎
只是要記得$f(0) = 1 \ \&\ f(1) = 0$
(其實只要把前幾項列出來就能大概猜到了)

就直接給他$DP$砸下去
要建表或不建表都過得了所以沒差

要滾動或不滾動都過得了所以沒差
只是如果不滾動就要用$vector$，陣列會爆

別忘了$mod\ 10^9+7$

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

constexpr LL mod = 1e9 + 7;

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        vector<LL> vec(N + 1, 0);
        vec[0] = 1;
        for(LL i = 2; i <= N; i ++ )
            vec[i] = (vec[i - 1] + vec[i - 2]) % mod;
        cout << vec[N] << endl;
    }
}

:::

`Time Complexity:` $O(TN)$
`Space Complexity:` $O(N)$

---

### $\color{red}{5\% + 20\% + 30\% + 35\% + 10\% = 100\%:\ 1 \leq N \leq 2^{31}-1}$

為什麼上面那個那麼紅勒
因為這個側資點大概只有`frankie`解得出來
應該可以說是這次的防破台側資點

先給大家科普一下「矩陣快速冪」是什麼
把遞迴式寫成矩陣乘法式
之後藉由快速冪將矩陣乘法加速
最後省下一大堆時間的$DP$優化

整體可以看去年講義的[這個](https://hackmd.io/@fdhscpp110/matix_fast_pow)

反正這個側資點就是必須用這個優化才能過去

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;
template<typename T> using Vec = vector<T>;
template<typename T> using Mat = Vec<Vec<T> >;

constexpr LL mod = 1e9 + 7;

inline Mat<LL> multi(Mat<LL> a, Mat<LL> b, LL x, LL y, LL z) {
    Mat<LL> ret(x, Vec<LL>(y, 0));
    for(LL i = 0; i < x; i ++ ) {
        for(LL j = 0; j < y; j ++ ) {
            for(LL k = 0; k < z; k ++ ) {
                ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    return ret;
}

inline Mat<LL> pwr(Mat<LL> a, LL b) {
    Mat<LL> r = {{1, 0}, {0, 1}};
    for(; b; a = multi(a, a, 2, 2, 2), b >>= 1) {
        if(b & 1)
            r = multi(r, a, 2, 2, 2);
    }
    return r;
}

inline LL Fib(LL n) {
    Mat<LL> r = {{1}, {1}}, a = {{1, 1}, {1, 0}};
    r = multi(pwr(a, n), r, 2, 1, 2);
    return r[0][0];
}

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N;
        cin >> N;
        if(N == 1) {
            cout << 0 << endl;
            continue;
        }
        if(N == 2) {
            cout << 1 << endl;
            continue;
        }
        cout << Fib(N - 3) << endl;
    }
}

:::

`Time Complexity:` $O(TlgN)$
`Space Complexity:` $O(1)$

---
---

## 更大堆的0與1

`tag: binary, 型態轉換, 卡記憶體, 11011111101010010`

給你$N$跟$K$
再給$2^N-K$個由$0,\ 1$組成的長度為$N$的不重複字串
輸出$K$個跟這些字串不一樣的「由$0,\ 1$組成的長度為$N$的字串」

---

某天我哥在跟我討論他出爛的某一題
我就在想能不能出個進階版然後讓他至少不是爛的
然後這題就出出來了

---

### $0\%:$ 基本常識 & 注意事項

「由$0,\ 1$組成的長度為$N$的不重複字串」
這個東西總共有$2^N$種

這算是基本常識，也可用排列組合來解釋
反正就是有$N$位，每位有$2$種狀態
所以是$2^N$種

所以題目可以看成
把所有沒列出的狀態列出來

喔然後記得壓$IO$優化

---

### $5\%:\ N = 3,\ K = 1$

$N=3$共有$8$種狀態：
$000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111$

然後可以用`set`維護有哪些還沒出現過
你要用`if`我也是沒差但我懶

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N, K;
        cin >> N >> K;
        set<string> st = {"000", "001", "010", "011", "100", "101", "110", "111"};
        for(LL i = 0; i < 8 - K; i ++ ) {
            string str;
            cin >> str;
            st.erase(str);
        }
        for(auto &i : st)
            cout << i << endl;
    }
}

:::

`Time Complexity:` $O(TN^22^N)$
`Space Complexity:` $O(2^N)$

---

### $5\% + 15\% = 20\% :\ N \leq 10$

$N=10$共有$1024$種狀態
太多了列不出來
所以這個時候只能用迴圈一個一個生

可以發現這些字串其實就是$0 \sim 2^N-1$的二進位
所以可以寫一個函式把十進位轉為二進位
像這樣

inline string d_to_b(LL num) {
    string str;
    while(num) {
        str += (num & 1) + '0';
        num >>= 1;
    }
    while(str.length() < N)
        str += '0';
    reverse(str.begin(), str.end());
    return str;
}

要注意的是要把前面不足的$0$補起來

然後求$2^N$可以用$pow(2,\ N)$這個函式
雖然不太好但因為$N$夠小所以還是準的

一樣用`set`維護有哪些還沒出現過

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

LL N, K;

inline string d_to_b(LL num) {
    string str;
    while(num) {
        str += (num & 1) + '0';
        num >>= 1;
    }
    while(str.length() < N)
        str += '0';
    reverse(str.begin(), str.end());
    return str;
}

int main() {
    IO;
    LL T;
    cin >> T;
    while(T -- ) {
        cin >> N >> K;
        LL M = pow(2, N);
        set<string> st;
        for(LL i = 0; i < M; i ++ )
            st.insert(d_to_b(i));
        for(LL i = 0; i < M - K; i ++ ) {
            string str;
            cin >> str;
            st.erase(str);
        }
        for(auto &i : st)
            cout << i << endl;
    }
}

:::

`Time Complexity:` $O(TN^22^N)$
`Space Complexity:` $O(2^N)$

---

### $5\% + 40\% = 45\%:\ N \leq 18,\ K = 1$

現在不能用`set`了，我有卡記憶體
但可以注意一件事，$K = 1$
這代表剩一個沒有出現

那我們這邊再給一個小常識
「在所有排列中，所有位數出現$0\ or\ 1$的個數都是$2^{N-1}$」
就以$N=3$來說
$000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111$
第一位為$0$的有$4$個，第一位為$1$的有$4$個
第二位為$0$的有$4$個，第二位為$1$的有$4$個
第三位為$0$的有$4$個，第三位為$1$的有$4$個

所以我們可以去記「第$i$位為$0$的有幾個」
是$2^{N-1}$的話答案的第$i$位就是$1$
反之就是$0$

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

int main() {
    IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL N, K;
        cin >> N >> K;
        LL arr[N], M = pow(2, N);
        for(LL i = 0; i < M - K; i ++ ) {
            string str;
            cin >> str;
            for(LL i = 0; i < N; i ++ )
                if(str[i] == '0')
                    arr[i] ++ ;
        }
        for(auto &i : arr)
            cout << (i == pow(2, N - 1) ? '1' : '0');
        cout << endl;
    }
}

:::

`Time Complexity:` $O(TN2^N)$
`Space Complexity:` $O(N)$

---

### $5\% + 15\% + 40\% + 40\% = 100\%:\ N \leq 18$

現在不能用`set`了，我有卡記憶體
也不能用$K = 1$的方法了

那我也懶得想怎麼講的比較好懂，因為懂得都懂
所以直接講解法

可以把每個輸入的字串想像成二進位，並把這些轉成十進位
然後用一個長為$2^N$的`bool`陣列去存有那些出現過
最後找沒出現過的然後把十進位轉成二進為後輸出就可以了

大概就是

bool arr[pow(2, N)] = 全都0;
while(bla bla bla) {
    cin >> str;
    LL num = 二進位轉十進位(str);
    arr[num] = 1;
}
for(LL i = 0, i < pow(2, N); i ++ )
    if(!arr[i])
        cout << 十進位轉二進位(i);

所以還要再寫一個函式是二進位轉十進位

inline LL b_to_d(string str) {
    LL r = 0;
    for(LL i = str.length() - 1, tmp = 1; i >= 0; i -- , tmp *= 2)
        if(str[i] == '1')
            r += tmp;
    return r;
}

大概就是這樣

:::spoiler code

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

LL N, K;

inline string d_to_b(LL num) {
    string str;
    while(num) {
        str += (num & 1) + '0';
        num >>= 1;
    }
    while(str.length() < N)
        str += '0';
    reverse(str.begin(), str.end());
    return str;
}

inline LL b_to_d(string str) {
    LL r = 0;
    for(LL i = str.length() - 1, tmp = 1; i >= 0; i -- , tmp *= 2)
        if(str[i] == '1')
            r += tmp;
    return r;
}

int main() {
    IO;
    LL T;
    cin >> T;
    while(T -- ) {
        cin >> N >> K;		
        LL M = pow(2, N);
        bool arr[M];
        memset(arr, 0, sizeof(arr));
        for(LL i = 0; i < M - K; i ++ ) {
            string str;
            cin >> str;
            arr[b_to_d(str)] ++ ;
        }
        for(LL i = 0; i < M; i ++ ) {
            if(!arr[i]) {
                cout << d_to_b(i) << endl;
            }
        }
    }
}

:::

`Time Complexity:` $O(TN2^N)$
`Space Complexity:` $O(2^N)$