# [solution] 2021-2022 ACM-ICPC Brazil Subregional Programming Contest

[TOC]

## pA
https://codeforces.com/gym/103388/problem/A
### 題意
給定有兩個正整數 $n$、$R$，以及 $n$ 個數值 $p_i$。

代表有 $n$ 個人，第 $i$ 個人排名第 $i$（排名約低代表越好），要給所有人禮物，但是第 $i$ 個人**至少**要給 $p_i$ 個，而且排名比較好的人不能拿的比排名較差的人還要少的禮物，最多給 $R$ 個。

問有多少種分配的方法數，$\bmod 10^9+7$。

### 測資範圍限制
- $1 \le n \le 5000$
- $1 \le R \le 10^9$
- $1 \le p_i \le 10^9$

### 解法
顯然的，若有 $p_i>R$，則答案為 $0$。

「因為排名比好的人不能拿的比排名較差的人還要少的禮物」，首先我們對 $p$ 反轉，再取前綴 $\max$，最後補上 $R$，這方便我們之後的操作。

:::info
範例

舉例來說：
$$
\begin{aligned}
p
&= [4, 8, 7, 6, 3]\\
&\Rightarrow [3, 6, 7, 8, 4] &\text{反轉整個陣列}\\
&\Rightarrow [3, 6, 7, 8, 8] &\text{取前綴 }\max \\
&\Rightarrow [3, 6, 7, 8, 8, 10] &\text{補上 }R \\
\end{aligned}
$$

待會都會用這個陣列舉例。
:::

### 重新建模

我們現在將整道題目建模成另外一道題目：

從起點開始，只能往右邊或往上走，且不能走到灰色區域，問走到終點的方法數。

也就是說第 $i$ 的行，必須最少要走道 $p_i$。
> 我懶得寫灰色區域的定義，可以自己感受一下，反正跟上面的 $p$ 是相關的。

巧妙的是，因為有了灰色區域的限制，因此每一個走法中，對於每個 $x=i$，他最高的 $y$ 就是 $i$ 被分配到的禮物。


現在最大的問題就是要怎麼算這道問題的方法數，雖然可以用 dp 計算，舉體的轉移類似 $dp[i][j] = dp[i-1][j]+dp[i][j-1]$ 的算法算，但是可以發現 $p_i$ 跟 $R$ 都很大，根本無法這樣做。

---

### 引入多項式

實際上，上面的這個 dp 想法是好的，讓我們看看在上面的圖做 dp 的效果。


若我們從左到右一行一行看 dp 值，可以發現到後一行就是前一行的前綴和（要把跑到灰色區域的 dp 值刪除）。

現在要引入一些多項式的操作，我們讓每一行都可以用一個多項式表達，第 $i$ 行得到的多項式 $f_i(x)$，代入 $j$ 就會得到第 $i$ 行第 $j$ 列的值。

顯然的第 1 行是一個零次多項式，因為後面的行都是前面一行的前綴和，所以會是前面一行的最高項 $+1$ 次多項式（也就是說從左到右依序是 $0, 1, 2, \ldots n$）次多項式。

拉格朗日差值法讓我們知道，給定 $N$ 個取樣點，就可以計算代表這些取樣點的多項式代入 $k$ 的值。現在我們的目標就是從我們知道的初始多項式，推到最後的 $n$ 次多項式，並計算 $f_n(R)$ 的值，就是答案了！

:::info
拉格朗日插值法

若給定 $n+1$ 個連續的 $x$ 的取樣點，則可以在 $O(n)$ 的時間計算 $k$ 在這 $n+1$ 個取樣點代表的 $n$ 次多項式代入的值。

這個的作法可以請讀者自己去搜尋。
:::

我們不妨直接在最一開始就取 $n+1$ 個取樣點，但這 $n+1$ 個取樣點要怎麼取比較好呢？會不會跑到灰色區域？下一章節將對這些問題做補充。

---

### 選擇取樣點

首先我們會將第 1 行的取樣點推到第 2 行，並重複直到第 n 行。

並且選哪些數當取樣點根本不會影響答案（但是要是連續的，因為複雜度要求）！因此我們可以挑一些 $x$ 很大的點當取樣點，這樣它們就不會跑到灰色區域。假設我們一開始取的點 $x$ 座標在 $[10^9, 10^9+n]$。

但是選擇那麼大的 $x$ 座標就會讓我們很難從第 $i$ 行推到第 $i+1$ 行，因為要計算第 $i+1$ 座標那麼高的取樣點，就要對整行做前綴和，這樣的時間複雜度無法接受。

用一張圖代表我們現在有的資訊：

其實不只這樣，我們還知道第 $i+1$ 行第 $p_{i}$ 列的值，因為他根本就跟第 $i$ 行第 $p_{i}$ 列的值一樣。

---
---
---
---
---
---
---
---
---

## pB
https://codeforces.com/gym/103388/problem/B

### 題意
給定一個字串長度為 $N$ 的字串 $S$，跟 $M$ 個字串 $T_i$。

對於 $S$ 的每一種旋轉 $R_1, R_2, \ldots, R_N$，設 $V_i$ 為 $\max\limits_{j \in [1, M]} lcs(R_i , T_j )$，其中 lcs 是 longest common substring 的意思。

目標求 $\min\limits_{i \in [1, N]} V_i$。

### 題目範圍限制
- $1 \le N \le 10^5$
- $1 \le M \le 10^4$
- $\sum\limits_{j \in [1, M]} |T_j| \le 10^5$

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

> 防爆雷

## 解法
先來想想要如何算出一個 $val_i$，我們可以令 $S = R_i+'\%'+T_1+'\%'+T_2+\ldots+T_M$ 塞入 Suffix Array，用 [這題](https://codeforces.com/edu/course/2/lesson/2/5/practice/contest/269656/problem/B) 的作法。

但這樣就需要 $O(N |S| \log |S|)$，顯然不夠快。

---

題目要求旋轉字串，不難想到將字串串成兩份相接的技巧，令 $P = S+S$。我們會希望可以一次計算所有 $V_i$。

首先，答案的值是否小於等於某個值 $x$ 具有單調性，觀察到這點之後不難想到二分搜。暫且讓我們定義 `check(mid)` 代表「是否存在一種旋轉 $R_i$，使得 $V_i$ 至多為 $mid$」

接著我們想要一次處理所有旋轉，因此可以設 $P = S+S$，這樣 $P$ 的每個長度為 $N$ 的字串都代表其中一個 $R_i$。這樣 `check(mid)` 就變成「==在 $P$ 中找到一個長度為 $N$ 的子字串，使得他對應到的 $V_i$ 至多為 $mid$==」。接下來的說明都會圍繞在這個問題上。

因為 `check(mid)` 有「至多」這個限制，因此對於所有 $1 \le i \le 2N$，我們會想知道 $P[i\ldots|P|-1]$，與所有 $T_j$ 的 LCS 最長是多少，並且這個 LCS 必須是從 $P[i]$ 作為開頭，這樣我們在選取長度為 $N$ 的子字串時，就可以避開一些不可選的字元，讓我們看下面的範例：


承上文，我們要選擇一個長度為 $N$ 的子字串，那麼：
- 我們知道從 $P[1...8]$ 可以找的最大 LCS 且從 $P[1]$ 開始的長度為 $4$，但是因為 $mid = 3$，因此可知如果要選 $P[1]$ 這個字元，則不則選到 $P[4]$ 之後的字元。
- 我們知道從 $P[4...8]$ 可以找到的最大 LCS 且從 $P[4]$ 開始的長度為 $2$，也就是說如果選到 $P[6]$，那麼選到 $P[8]$ 以後的字元都是沒關係的，因為不會違反 LCS 至多是 $mid$ 的限制。

根據上面的推論，我們知道對於 $P$ 中的每個字元，我們都可以找到一個右界 $bound_i$，代表如果選了 $P[i]$ 這個字元，則只能選到 $bound_i$ 這個字元以內。

現在，我們希望找到一個長度為 $N$ 的區間 $[i, i+N-1]$，$\min\limits_{j \in [i, i+N-1]} bound_j \ge i+N-1$。這件事情可以輕鬆用 $O(n)$ 找到，就留給讀者自行思考了。

整個作為為 $O(\log n)$ 的二分搜乘上，

---
---
---
---
---
---
---
---
---

{%hackmd @temmie950807/r1KCzgjFh %}
{%hackmd @temmie950807/Prove_Style %}