---
# System prepended metadata

title: 演算法學習筆記 | by PeterOOO

---

# 演算法學習筆記 | by PeterOOO

# 資料結構

> 資料結構可以很大程度地加速演算法
> 資料結構就是為了加速搜尋和有效儲存而生
> 以下為好用的資料結構



| 名字 | 說明 | 注意 |
| -------- | -------- | -------- |
| STL-multiset/set     | 內建的二元搜尋樹，用來加速搜尋大於等於k的最小值  |   !!! 不可搜尋第k小  |
|  STL - map  |   可以當字典用的容器，預設為0   |      |
|  STL-priourity_queue              |        在需要大量`pop`的場合比set快                |   `pop` 為 $O(1)$，只能存取極值     |
|    pbds-tree     |     進階的set，可以搜尋第k小        |      常數比set大，通常用treap更靈活      |
|         treap 樹堆      |    進階結構，用 `merge-split` 完成所有操作         | 時間複雜度跟樹高相關，通常比 $logn$ 慢一點 |
|      segment tree 線段樹      |          一種分治的資料結構，常用於可快速合併的區間問題      |    儲存空間大、常數大            |
|      sparse table 倍增表           |        除了做區間問題，還可以做模擬走路             | 空間複雜度大，需 $O(nlogn)$           |
|        trie字典樹           |         查詢前綴字串數量                   |          基礎版時間複雜度差，<br>  查詢$O(T)$ 插入$O(T)$ T是單次操作的字串長度          |



# 二分搜
:::success
把問題轉換成是否問題
尋找是否交界
:::
:::spoiler 實作
找大於等於目標值的最小值的==位置指標==
```cpp=
lower_bound( v.begin(),v.begin()+n, target )
```
找大於目標值的最小值的==位置指標==
```cpp=
upper_bound( v.begin(),v.begin()+n, target )
```

:::
### 例題
:::info
尋找數列 1,2,4,7,8,9 中大於5的數字的數量
:::
:::success
轉成是否問題 ， if $ai$ > 5 ，如下
:::
| 1 | 2  | 4 | 7 | 8 | 9 |
|--|--|--|--|--|--|
| F | F  | F | T | T | T |

用 upper_bound() 得到第4位，可知有 6 - 4 + 1 個

-----

# 遞迴

## 核心精神: 把大問題切成小問題

### 經典1 河內塔問題
:::spoiler 題敘
有3根柱子，共有$n$個環在1號柱，全部移動到3號柱要怎麼移動?
限制:小的環一定要在大的環上面。
一開始所有環上到下由小到大。
:::
### 解法
有n個環要移到3號柱，一定要先把上面n-1個環移動到2號柱
再將底下的一個移到3號柱，再把2號柱的n-1個環移到3號柱

所以:
有2個環時，用3步就可以解決
有3個環時，用7步就可以解決
.......
......
有n個環時，用$2^n-1$步就可以解決

### 實際操作:

$f(n)$ 代表n個環要做$f(n)$ 次
$f(n)$ = $f(n-1)+1+f(n-1)$ 當$(n>=2)$

### 練習題 : [河內之塔-蘿莉塔](<https://tioj.ck.tp.edu.tw/problems/1355>)

:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;

int n,step;

void solve( int num, int nowstk , int frestk ,int tarstk ){
            //數量    現在         空的        目標
    if(n==1){
        cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<tarstk<<'\n';
        return ;
    }
    if( num ==2 ){
        cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<frestk<<'\n';
        cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<tarstk<<'\n';
        cout<<"#"<<++step<<" :"<<" move the dish from #"<<frestk<<" to #"<<tarstk<<'\n';
        return;
    }
    solve( num-1, nowstk , tarstk , frestk );
    cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<tarstk<<'\n';
    solve( num -1 , frestk , nowstk ,tarstk);
    return;
}

int main(){
    cin >> n;
    solve(n,1,2,3);
}
```

:::

----

# 快速冪
:::info
如何計算$a^b$
:::
$\mathcal{O}(b)$作法:
```cpp=
int a = 1;
for( int i =0 ; i<b; i++ ) a*=a
```
運用快速冪做到$\mathcal{O}(\log{} b)$
:::info
根據指數律我們得知 $a^b$ = $a^{b/2}$ * $a^{b/2}$ 
c++ 的除法在正數時會向0取整數
所以在b是奇數時要多乘一次
ex: $2^7$ = $2^3$ * $2^3$ * 2
:::
遞迴版:
```cpp=
int quick_power( int a , int b ){
    if(b==0) return 1;
    int tmp = quick_power( a , b/2 );
    if( b%2==1 ){
        return tmp * tmp * a;
    }else{
        return tmp * tmp;
    }
}
```
迴圈版
```cpp=
int quick_power( int a , int b ){
    int k = a,x = 1;
    while( b > 0 ){
        if( b & 1 ){
            x *= k;
        }
        b>>=1;
        k=k*k;
    }
    return x;
}
```

# 模逆元 | 用費馬小定理

在$a$、$p$互質且$p$為質數時
$a^{p-1} ≡ 1$ $(mod$ $p)$
翻成中文: $a$的$p-1$次方在模$p$時同餘1

如果要計算

$a^{-1} (mod$ $p)$ 直觀，因為$a^{-1}$是有小數點
根據 $a^{-1}$ $(mod$ $p)$ = $a^{-1} \times 1$ $(mod$ $p)$
帶入費馬小定理得: $a^{-1} \times a^{p-1}$ $(mod$ $p)$ $≡$ $a^{-1}$ $(mod$ $p)$
因此
$a^{p-2}$ $(mod$ $p)$ $≡$ $a^{-1}$ $(mod$ $p)$

計算$a$的$p-2$次方即可
# 倍增表 Sparse Table

## 核心精神

先算好跳躍$2^k$步的值
每次詢問從表中組合出答案
## 適用情境

1. 內容不會變
2. 多筆詢問
3. 所求可以從兩區塊快速合併

## 複雜度

時間複雜度:$O(nlogn + qlogn)$
空間複雜度:$O(nlogn)$

### 為什麼要存 nlogn 

> 因為我們儲存從i開始往前$2^k$
> 而總結點數為n時， $2^k \le n$  ，因此n個點最多要存`logn` 個結果，總結為`( nlogn )`

## [應用1. 區間最小值 RMQ](<https://cses.fi/problemset/task/1647>)
:::spoiler 題敘
給你一個數列 $a$ 
有$q$筆詢問，輸出$[a,b]$內最小值
:::

### 建立一個倍增表
我們建立的一個表，
跳躍$2^k$的區間最小 $[ a_x$ , $a_x + 2^k ]$ 

數列: 1 , 5 , 4 , 2 , 3

| 起點 | 1 | 2 | 3 |  4  | 5  |  
| -------- | -------- | -------- |------| ------| ------|
| 跳躍$2^0$區間最小     | 1 | 4 | 2 | 2 | 3 |
| 跳躍$2^1$區間最小     | $min(1,2)$ | $min(4,2)$ | $min(2,3)$ | $min(2,3)$ | $min(3,3)$ |
| 跳躍$2^2$區間最小     | $min(1,3)$ | $min(2,3)$ | $min(2,3)$ | $min(2,3)$ | $min(3,3)$ |

### 實作細節
1. $a_n$跳躍$2^k$ 取最小 = $a_n$跳躍$2^{k-1}$ 和 $a_{n+2^{k-1}}$ 跳躍$2^{k-1}$  取最小

2. 如果$a_{n+2^{k-1}}$ 超出陣列大小，就用$a_n$
3. $a_n$ 不管跳多遠，最小值一定是$a_n$


:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int st[25][200005];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;
    cin >> n >> q;
    vector<int> arr(n+1);
    for( int i=1; i<=n;i++ ) cin >> arr[i];
    for( int i =1; i<n; i++ ) {
        if( arr[i] <arr[i+1] ){
            st[0][i] = i;
        }else{
            st[0][i] = i+1;
        }
    }
    st[0][n] = n;
    for( int i =1; i<=20; i++ ){
        for( int j  =1 ; j<=n; j++ ){
            int a = st[i-1][j];
            int b = st[i-1][min(j+(1<<(i-1)),n)];
            if( arr[a]<arr[b] ) st[i][j] = a;
            else st[i][j] = b;
        }
    } 
    // for( int i =1; i<=n; i++ ){
    //     for( int j = 0; j<=4; j++ ){
    //         cout<<st[j][i]<<' ';
    //     }
    //     cout<<endl;
    // }
    while(q--){
        int a,b;
        cin >> a >> b;
        if( a==b ){
            cout<<arr[a]<<'\n';
            continue;
        }
        int jump = b-a;
        int result = (31 - __builtin_clz(jump));
        int j = (1<<result) *( a!=b );
        int fin = min(arr[st[result][a]],arr[st[result][max(b-j,1)]]);
        cout<<fin<<'\n';
    }
}
```
:::


## [應用2. 最近共同祖先 LCA](https://cses.fi/problemset/task/1688)

::: info
1 是董事長，2 ~ n是他的員工，給你2 ~ n的上一級主管(每一人的上一級只有一個)
有Q次詢問: 員工 a 和 員工 b 共同的主管中最低級的主管 ?
:::


在這個題目中，可以知道員工的上下級關係是一棵樹
我們紀錄從每個點往上跳$2^k$的點是誰

:::danger
注意:1的上級我們設為1，以維護不越界
:::
根據精神，建立st表後
如何計算a、b的LCA呢?
有以下兩種情況，我們先來看工具

### subtask : 如何判斷B是否為A的上司之一
導入dfs序的想法，dfs的先後可以判斷是否在同一條上的上級
因為若是B為A的上司，B的進入時間必小於A的進入時間，且B的跳出時間必大於A的跳出時間，也就是說以下判斷是否成立

```cpp!
tin[B] < tin[A] && tin[B] > tin[A] 
```


![image](https://hackmd.io/_uploads/r1yoUDRVxg.png)



**若 ab互為LCA**

![image](https://hackmd.io/_uploads/HJce4PRVlg.png)
定義 `LCA(a,b)` 為a、b的LCA

此時， LCA(a,b) = a、b中最上層的那個

**若 ab的LCA不是a或b**

![image](https://hackmd.io/_uploads/ryvSEwA4gx.png)
LCA(a,b) = 同時是a、b上司的最低點

### 如何找LCA?
假設a有上司 X 和 Y ，且Y比X上級，
`如果Y不是b的上司，那X也不是`
`如果X是b的上司，那Y也是b的上司`
也就是說LCA有**單調性**
只要X不是共同祖先，X的下級一定不是共同祖先
因此我們從a的第$2^{20}$個上司開始嘗試
若上司是共祖，就不跳
若上司不是共祖，就不跳
反覆做20次後，會得到LCA(a,b)下一級
因此要再跳1
:::spoiler AC code

```cpp=
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
#define LL long long
vector<int> tin,tout; //時間戳
int timer =0; //計時器
vector<int> pa; //上一級
vector<vector<int>> G; 
 
void dfs( int a  ){
    
    tin[a] = ++timer;
    for(auto xx : G[a]){
        if( xx == pa[a] ) continue;
        dfs( xx ); 
    }
    tout[a] = ++timer;
}
 
int is_anc( int a, int b ){
    if( tin[a] <= tin[b] && tout[a] >= tin[b] ){
        return 1;
    }
    return 0;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;
    cin >> n >> q;
    pa.resize(n+1);
    G.resize(n+1);
    tin.resize(n+1);
    tout.resize(n+1);
    vector<vector<int>> st(25,vector<int>(n+1));
    pa[1] = 1;
    for (int i = 2; i <=n; i++)
    {
        cin >> pa[i];
        G[pa[i]].push_back(i);
    }
    for (int i = 1; i <=n; i++)
    {
        st[0][i] = pa[i];
    }
    //建構倍增表
    for (int j = 1; j <=20; j++)
    {
        for (int i = 1; i <=n; i++)
        {
            st[j][i] = st[j-1][st[j-1][i]];
        }
    }
    dfs(1);
    for (int i = 0; i < q; i++)
    {
        int a, b;
        cin  >> a >> b;
 
        if ( is_anc(a,b) ){
            cout<<a<<'\n';
            continue;
        }       
        if( is_anc(b,a) ){
            cout<<b<<'\n';
            continue;
        }
 
        int nb = a;
 
        for (int j = 20; j >=0; j--)
        {
            if( !is_anc(st[j][nb] , b)  ){
                nb = st[j][nb] ;
            }
        }
 
        cout<<st[0][nb]<<"\n";     
    }
    return 0;
}
```

:::

# 動態規劃

## o/1背包
### 狀態: 前i個物品在重量W下的最大價值
----
## 有限背包

::: spoiler 題敘

#### 給你$n$種物品每一種物品有$C$個，一個物品重$W$、價值$V$
#### 一個背包只能裝重量$T$以下，最大價值是多少?

:::

::: spoiler 限制
    
#### 所有數字為正整數

#### 0 < $n\times T$ <1e7
#### 0 < C、W、V < 1000

:::

## <font color = #ffda33> 二進制優化 </font>
### 作法:將數量轉成$2^k$相加，然後分開做0/1背包
### 想法?:
### EX : 7 = 1 + 2 + 4
### 或是說任何數字都可以轉成2進制
## <font color = #ffb0c0> 思維陷阱 </font>

思考一下 如果有7個要怎麼試
如果是6個用你的想法會對嗎?

:::warning 
### 錯誤想法

如果是7個，那就從$2^0$開始試放1、2、4 ... $C'$，直到 $C'$ > 7
:::

#### 聰明的你一定發現了當$C$是$2^n-1$時以上是對的
#### 但是當$C$=6時 ， 也是試 1、2、4 ，但是實際上是不能做1+2+4的，因為如果$C$不是$2^n-1$，那$C$的二進制一定有至少一位是0。所以全部舉出來會多舉($>C$)。

## 改進想法

### 假設我們有6，只要可以組出3以下的$2^k$+3就能湊出1~6

![有限背包1](https://hackmd.io/_uploads/B1JpBdot1e.png =500x400)


### 因為每次可以湊出的範圍會$\times 2$如果 現在的範圍$\times 2$ 小於$C$
### {那現在的範圍} + {$C -以前範圍的總和$} 這些數一定可以湊出$C$以下全部的數

### 因為 現在的範圍必 >= $\frac{C}{2}$ 才會不能舉下一個2進位

### 所以$C-$現在範圍的總和這個數 搭配現在已經舉過的$2^k$ 就可以湊出$1$~$C$

### 例題

[Striker的秘密 - EXTREME](<https://tioj.ck.tp.edu.tw/problems/1407>)

----
## 無限背包
#### 練習題: [CSES Dice Combinations](https://cses.fi/problemset/task/1633)
[參考連結](https://hackmd.io/@Paul-Liao/SJHC9SE0u#%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C%E5%80%91)

----

## LIS 最大遞增序列

:::info 
對於數列 $a$ 最長的嚴格遞增數列長度為?
:::

:::warning
example

INPUT:
5
1 5 3 6 7
OUTPUT:
4
:::

## 基本想法 時間複雜度$O(n^2)$
對於每個位置我們都試試看把它當成結尾
考量以當前的位置最長可以接誰?


| 位置 | 位置1 | 位置2 | 位置3 | 位置4 | 位置5 |
| -------   | -------- | -------- | -------- |-------- | -------- |
|  值  | 1     | 5     | 3     | 6     | 7     |
| 可接的值   | x     | 1     | 1     | 1、3、5 | 1、3、5、6     |
|  最佳長度  |  0+1  |  1+1  |  1+1  |   2+1  |  3+1    |


## 進階想法 時間複雜度$O(nlogn)$

觀察:
對於每個位置為結尾，接在<$a_i$ 的最大值後一定是最好的

因為LIS有單調性，因此用二分搜<$a_i$ 的最大值
我們可以維護一個vector儲存目前看到最好的LIS

過程:

LIS : 1  
LIS : 1 5
LIS : 1 3 <-把5換成3
LIS : 1 3 6
LIS : 1 3 6 7
LIS陣列長度為最大LIS長度


----

# 圖論

## 深度優先搜尋DFS

## 廣度優先搜尋BFS

## 進階版BFS - dijkutra 算法

### 限制

- 所有邊非負權重

### 練習題
:::success
**基本題**
[CSES Shortest Routes I](<https://cses.fi/problemset/task/1671/>)

**變化題**
[leetocde 1368 (名字太長)](<https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/>)

:::
:::warning
**進階題**
[ABC_E-Flip Edge](<https://atcoder.jp/contests/abc395/tasks/abc395_e>)

[題解](https://hackmd.io/@PeterOOO/Sk5iqWsi1e)
:::
## 最小生成樹
### Kruskal法
從最小的邊 ( a 到 b 長度 c )開始
若 a b 連通，不處理
若 a b 不連通，花費 c 連接a b 
### 核心code
Union連接a b 
Fa 取得 a b 的區塊，用par存父節點的區塊，初始自己為一區塊
```cpp=
int Fa( int a ){
    if( par[a] == a ) return a;
    return par[a] = Fa(par[a]);
}

void Union( int a , int b ){
    int Fa = F(a);
    int Fb = F(b);
    par[Fa] = Fb;
}
```
## SCC點強連通分量
:::info
給你一個有向圖(無重邊)，
定義一個SCC為SCC中每個點都可以走到彼此
假設$u$、$v$在一個SCC，
$u$一定可以走到$v$
$v$一定可以走到$u$
試求每個點的SCC編號
:::

### 例題
:::info
[Planets and Kingdoms](https://cses.fi/problemset/task/1683)
:::


## SCC-Tarjan
參考文章:
首先來認識樹的邊 [圖來源](https://determined-wiles-eb7bd3.netlify.app/graph/connectivity/)
![dfsEdge](https://hackmd.io/_uploads/rkaJteWrge.png)

* tree edge - dfs下去的邊
* cross edge - 已經走過但是不是父節點
* back edge - 已經走過的父節點
* forward edge - 已經走過的子(孫)節點

tarjan 算法基於 $low$ 和 $dfn$ 計算
$dfn$ : dfs的順序
$low$ : 不經過來的tree edge可走到的最小$dfn$

### 作法

每次dfs將點$u$ push 到stack
初始化 dfn[u]，low[u] = dfn[u]
往下dfs，再依照邊縮緊low[u]
當low[u] = dfn[u]時
u為scc最後一個點，所以從stack中移除u以下的節點。
### 邊的處理

每次dfs的時候
若 v 沒拜訪過 ( tree edge )
    
    dfs(v) 後 low[u] = min( low[u], low[v] )
若 v 有拜訪過
且 v 在stack中( back edge )

    low[u] = min( low[u],low[v] )
且 v 不在stack中 ( cross edge )
    
    u、v 必不在同一SCC，不做操作

### 參考程式

:::spoiler code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
#define LL long long
vector<vector<int>> G;
vector<int> vis,id,dfn,low,instk;
stack<int> tarstk;
int idx ;
int timer;

void dfs( int a ){
    dfn[a] = ++timer;
    low[a] = timer;
    vis[a] = 1;
    instk[a] = 1;
    tarstk.push(a);

    for(auto xx : G[a]){
        if( vis[xx] ){
            if( instk[xx] ){
                // back edge
                low[a] = min( low[a],low[xx] );
            }else{
                //cross edge
                // low[a] = min( low[a],low[xx] );
            }
        }else{
            dfs(xx);
            low[a] = min(low[a],low[xx]);
        }
    }

    if( low[a]==dfn[a] ){
        ++idx;
        while( tarstk.top()!=a ){
            id[tarstk.top()] = idx;
            instk[tarstk.top()] = 0;
            tarstk.pop();
        }
        id[a] = idx;
        instk[a] = 0;
        tarstk.pop();
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;
    idx = 0;
    cin >> n >> m;
    G.resize(n+1);
    dfn.resize(n+1);
    low.resize(n+1);
    id.resize(n+1);
    vis.resize(n+1);
    instk.resize(n+1);
    for (int i = 0; i < m; i++)
    {
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    for (int i = 1; i <=n; i++)
    {
        if( !vis[i] )
            dfs(i);
    }
    
    cout<<idx<<'\n';
    for (int i = 1; i <=n; i++)
    {
        cout<<id[i]<<' ';
    }
    
    return 0;
}

```
:::

## SCC-Kosaraju

參考文章: [強連通分量](https://hackmd.io/@nehs-iced-7th/HkNfoOMUF?print-pdf#/)

:::success
用兩次DFS
第一次紀錄便歷順序
然後從最後的子節點開始做第二次DFS
:::
### 原理
:::warning
一個SCC中任一點$u$都可以到在SCC中的其他點$v$
同時，$v$ 也可以到 $u$
如下圖有2個SCC
:::
![CF2051D_1](https://hackmd.io/_uploads/B1xtdn2Pkg.png =300x300)


:::warning
對每一個SCC我們可以由DFS把它轉成一棵樹
遍歷成 A->C->B->D->E
:::

觀察正反圖
<figure class="half">
    <img src="https://hackmd.io/_uploads/S1fCdh3vkx.png" width =300 height=300>
    <img src="https://hackmd.io/_uploads/SJWJ82nP1e.png" width =300 height=300>
</figure>

加上DFS的順序(類似樹壓平)
![CF2051D_4](https://hackmd.io/_uploads/Bk8e_n3DJx.png =300x300 )
我們得知對每一塊SCC的根($A$)和最後一個節點($B$)
在圖翻轉後會互換順序
翻轉後DFS走到的點即是同SCC

第一次DFS的遍歷順序
    
    A C B D E

我們會發現 A CB A DE 是一棵樹
而且B、E是最後走到的點
如果從B開始可以走回A、C那BAC是一塊SCC
所以反過來，做DFS

### 作法
1. 第一次DFS儲存每個點的順序
2. 第二次DFS要從最後看到的節點用反向圖DFS、紀錄SCC
3. DFS2中如果下一點沒看過->DFS2
    如果看過->它已經是SCC故不理它
:::spoiler code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
#define LL long long
 
int n,m,cnt;
vector<vector<int>> PG,RG;//RG:逆向圖
vector<int> SCC,vis;
vector<int> path; // save dfs1 order
void dfs1( int a ){
    vis[a] = 1;
    for( int x : PG[a] ){
        if( !vis[x] ){
            dfs1(x);
        }
    }
    path.push_back(a);
}
 
void dfs2( int a ){
    vis[a] = 0;
    SCC[a] = cnt;
    for( int x : RG[a] ){
        //if haven't vis by dfs2
        if( vis[x] ){ 
            dfs2(x);
        }
    }
}
 
void kosaraju(){
    for( int i =1; i<=n; i++ ){
        if( !vis[i] ){
            // cout<<i<<" not visit"<<endl;
            dfs1(i);
        }
    }
    for ( int j = path.size()-1; j>=0;j-- )
    {
        int i = path[j];
        if( vis[i] ){
            ++cnt;
            dfs2(i);
        }
    }
    cout<<cnt<<'\n';
    for (int i = 1; i <=n; i++)
    {
        cout<<SCC[i]<<' ';
    }
    cout<<endl;
    
    
    
}
 
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cnt = 0;
    cin >> n >> m;
    vis.resize(n+1);
    vis.assign(n+1,0);
    SCC.resize(n+1);
    for( int i =0; i<=n; i++) SCC[i] = 0;
    PG.resize(n+1);
    PG.assign(n+1,vector<int>({}));
    RG.resize(n+1,{});
    for( int i = 0; i<m; i++ ){
        int a,b;
        cin >> a >> b;
        PG[a].push_back(b);
        RG[b].push_back(a);
    }
    kosaraju();
    return 0;
}

```
:::
