比賽補題紀錄

ICPC - Universal Cup

Season 3

ICPC - Africa and Arab

ICPC - Asia East Continent

Final

ICPC - Asia Pacific

Championship

Indonesia

Japan

South Korea

Taiwan

Vietnam

ICPC - Asia West Continent

ICPC - Europe

ICPC - Latin America

Championship

ICPC - North America

ICPC - Northen Eurasia

ICPC - South Pacific

ICPC - Other

註釋

1. 不一定會每題（每個 subtask）都寫題解，有些太枯燥的或沒有啟發性的會被跳過。
2. 有酷炫實作方法的可能會被特別提到，否則像一些 casework DP 就自己看 submission 就好。

我的題目

因為出了好多題目好像都沒有寫好題解，決定來整理一下，但優先級不高。

• 0x00 ~ 0x08 待補
• IONCamp 2022 ~ 2024 待搬運
• 全國模擬賽 2021 ~ 2023 待搬運
• YTP 2023 ~ 2024 待搬運
• 演算法概論 待補
• 還有許多......
• 目前總共應該是 120 題，不知道要補多久......

The 3rd Universal Cup. Stage 3: Ukraine

• 連結：https://qoj.ac/contest/1714
• 時間：2024 Oct 30, 17:40-22:40
• 團隊：ネクロマンサー (SorahISA)
• 成績：7 / 12, Penalty 910, dirt 12% ( A B C D E F G H I J K L )

第一篇做題筆記，不以時間軸的方式記錄比賽，只記錄解題過程。

這場難度在 UCup 中算很低，最強的 USA1 甚至在兩個小時以內就破台了。

Problem A. Aibohphobia

Tags: casework, palindrome

給定字串 $s$，請將其重新排列使每個長度 $\ge 2$ 的前綴都不是回文。

• 多筆測資、$\sum |s|\le 10^6$

顯然只有一種字元無解，當有兩種字元的時候要 $s_1\ne s_2$、$s_1\ne s_3$、$\dots$，可以得到必須要有某個字元只出現一次，否則無解。

當有三種以上的字元時，將字串排序並 reverse(1 + ALL(s)) 後輸出即可。

Problem B. Breaking Bad

待補

給定一個 $n\times n$ 的矩陣 $A$，請問在所有 $1,2,\dots ,n$ 的排列 $\sigma$ 中，$\left({\sum }_{i=1}^n{A}_{i,{\sigma }_i}\right)\mathrm{mod}5$ 可能有哪些值。

• $n\le 1000$

Problem C. Chemistry Class

Tags: greedy

給定 $2n$ 個整數 $a_1<a_2<\cdots <a_{2n}$，請將其兩兩配對滿足

• 不存在差距 $>A$ 的配對（不合法）
• 差距 $\ge B$ 的配對數量盡量多（好配對）

• 多筆測資、$\sum n\le 200000$、值域 $[1,10^{18}]$

以下令差距在 $(B,A]$ 之間的配對為 壞配對。

以下令 $i_1<i_2<i_3<i_4$，觀察：

• 當配對 $(i_1,i_3)$ 及 $(i_2,i_4)$ 合法，則改成 $(i_1,i_2)$ 及 $(i_3,i_4)$ 也合法。
• 當配對 $(i_1,i_4)$ 及 $(i_2,i_3)$ 都是好配對，則改成 $(i_1,i_2)$ 及 $(i_3,i_4)$ 也是好配對。
• 當配對 $(i_1,i_4)$ 及 $(i_2,i_3)$ 都是壞配對，則改成 $(i_1,i_2)$ 及 $(i_3,i_4)$ 也仍然合法。

因此，可以得出以下性質：

1. 配對不會相交，可以看成括弧序列。
2. 好配對不會包著任意配對，也就是說好配對一定是 $(p,p+1)$ 的形式。
3. 壞配對只可能包著好配對，也就是說一定是 BGG...GGB 中間有偶數個 G 的形式。

採用 greedy 配對的方式，由左至右配對 GG，當不會讓壞配對 B...GGB 差距超過 $A$ 時就配對，否則就配對壞配對。

因為這總是保證了最多的好配對，所以 greedy 可以得到最佳解。

Problem D. Daily Disinfection

Tags: casework

給定長度 $n$ 的 $01$ 字串 $s$，每次可以交換相鄰兩個字元，求最少交換次數使每個位置都出現過至少一次 0。

• 多筆測資、$\sum n\le 200000$

每個 1 都一定要移開，假設 $s_1=$ 0 那每個 1 都一定能往右移動。

觀察到只有在 1.101.101.101.1 這種 case（頭尾都是 1 且沒有連續的 0）才會讓 1 必須被挪動第二次，此時一定是挪動最小塊的連續 1。

Problem E. Equalizer Ehrmantraut

Tags: math

請求出有多少個長度為 $n$ 的整數序列對 $(⟨a⟩,⟨b⟩)$ 滿足 $1\le a_i,b_i\le m$ 且對所有 $1\le i<j\le n$ 皆有 $\min (a_i,b_j)=\min (a_j,b_i)$。

模 $998244353$ 輸出。

• $1\le n,m\le 10^6$

長一樣當然都是合法的，考慮當有數字不同的時候，W.L.O.G. $a_p>b_p$ 是第一個不同的位置且 $⟨a⟩$ 非嚴格遞增：

• 此時 $b_{p+1}$ 一定等於 $b_p$，由 $b_p<a_p\le a_{p+1}$ 可以推得 $[\min (a_{p+1},b_p)=b_p=\min (a_p,b_{p+1})<a_p]⟹[b_p=b_{p+1}]$。
• 此時 $b_p$ 一定 $\ge b_{p-1}$，由 $b_{p-1}=a_{p-1}\le a_p$ 可以推得 $[\min (a_{p-1},b_p)=\min (a_p,b_{p-1})]⟹[b_p\ge b_{p-1}]$。

也就是合法的序列對長相是 $(⟨a⟩,⟨\min (a,x)⟩)$。枚舉 $⟨a⟩$ 中的最大值 $x$ 後可以得到答案：

$$\sum _{x=1}^m(x^n-(x-1{)}^n)\cdot (2x-1)$$

即可 $\mathcal{O}(m\log n)$ 求解。

Problem F. Formal Fring

待補

定義 $f(n)$ 是非負整數集合 $S$ 的數量，滿足 ${\sum }_{s\in S}{2}^s=n$ 且不存在 $\varnothing ⊊T⊊S$ 使得 $\lfloor {\log }_2\left({\sum }_{t\in T}{2}^t\right)\rfloor =\lfloor {\log }_2\left({\sum }_{u\in T\setminus S}{2}^u\right)\rfloor$。

請求出 $f(1),f(2),\dots ,f(X)$ 模 $998244353$ 的值。

• $X\le 10^6$

Problem G. Goodman

AC 但還不會證明，待補

定義兩個 $1,2,\dots ,n$ 的 permutation $p,q$ 的複合 $⟨p\circ q⟩$ 為 $(p_{q_1},p_{q_2},\dots ,p_{q_n})$。

給定一個排列 $p$，請求出一個排列 $q$ 使 $|\text{LCS}(⟨q⟩,⟨p\circ q⟩)|$ 最大。

• 多筆測資、$\sum n\le 10^6$

Problem H. Highway Hoax

Tags: dp, ntt

給一棵 $n$ 個點的樹，邊是有向的，一開始有某些位置各有一個棋子，每次操作可以將一個棋子沿著出邊移到相鄰的點，但移動完後會將邊反轉。

定義合法狀態是每個點的棋子數量皆 $\le 1$，求從原始盤面可以抵達多少種合法狀態。

模 $998244353$ 輸出。

• $2\le n\le 200000$

先觀察到任意邊 $(u,v)$ 只會有至多一次的 $u\to v$ 操作，移回去再移回來並沒有意義。當對這棵樹定根後，會具有以下性質：

• 合法狀態下，每個子樹的棋子數量必定是原始棋子數量 $\pm 1$ 以內，取決於跟父親連邊的方向。

這就會想使用 DP 解決：令 ${\text{dp}}_{v,+/0/-}$ 代表以 $v$ 為根的子樹，且 $v$ 有多一個 / 剛剛好 / 少一個棋子的合法狀態數量。這樣就可以得到以下轉移：

待補

每個小孩的 DP 值對應到多項式 $({\text{dp}}_{v,+})\cdot x^1+({\text{dp}}_{v,0})\cdot x^0+({\text{dp}}_{v,-})\cdot x^{-1}$。

轉移可以把所有小孩的多項式 offset 一個 $x^1$ 之後 NTT 乘起來，但要注意要每次挑最短的兩個多項式做 NTT，否則複雜度仍會退化為 $\mathcal{O}(n^2)$。

一個方便的 $\mathcal{O}(n{\log }^{2}n)$ trick 是把所有多項式丟進 queue（deque）裡，每次取出前兩個做事之後再放到最後面，這個的複雜度可以透過參考線段樹的長相感性證明。

Problem I. Increasing Income

Tags: dp

定義兩個 $1,2,\dots ,n$ 的 permutation $p,q$ 的複合 $⟨p\circ q⟩$ 為 $(p_{q_1},p_{q_2},\dots ,p_{q_n})$。

給定一個排列 $p$，請求出一個排列 $q$ 使 $f(⟨q⟩)+f(⟨p\circ q⟩)$ 最大。

• $f(a_1,a_2,\dots ,a_k)$ 是 $\#\{i:\forall j<i.a_i>a_j\}$，也就是前綴最大值數量。

• 多筆測資、$\sum n\le 10^6$

• $\text{Claim 1.}$ 首先，一定有下界 $n+1$ 跟上界 $n+|\text{LIS}|$。

現在考慮如何構造滿足上界的答案，首先先把 LIS $L$ 抓出來（$L=(p_{i_1},p_{i_2},\dots ,p_{i_k})$ 滿足 $i_1<i_2<\cdots <i_k$ 且 $p_{i_1}<p_{i_2}<\cdots <p_{i_k}$）。

接著要處理剩下的元素，先 獨立 觀察 $p_i$ 可以放的位置：

• 在不破壞 $L$ 的貢獻的前提下插進 $L$ 裡面：當滿足 $i<i_j$ 且 $p_i<p_{i_j}$ 時可以將 $p_i$ 放到 $p_{i_{j-1}}$ 跟 $p_{i_j}$ 中。
• 在讓自身能產生貢獻的前提下插進 $L$ 裡面：當滿足 $i>i_{j-1}$ 或 $p_i>p_{i_{j-1}}$ 時可以將 $p_i$ 放到 $p_{i_{j-1}}$ 跟 $p_{i_j}$ 中。

總上兩點，可以得到當 $p_i$ 放在滿足 $i<i_j$ 且 $p_i<p_{i_j}$ 的最小的 $j$ 前面就能不破壞原有的貢獻並維持自身的貢獻。

如果有多個 $p_i$ 可以放在 $p_{i_{j-1}}$ 跟 $p_{i_j}$ 之間，這些數字必定可以被分到兩類：$i>i_{j-1}$ 跟 $p_i>p_{i_{j-1}}$。每個數字必定且只滿足其中一個條件（否則就不會被放在這裡），只要確保所有第一類的數字依照位置 $i$ 排序、第二類的數字依照值 $p_i$ 排序，就能保證所有區間內的數字都有貢獻。

時間複雜度：$\mathcal{O}(n\log n)$。

Problem J. Jesse's Job

Tags: N/A

給定一個排列 $\sigma$，你要將排列中的元素塗上黃色 Y 或紅色 R（至少各一），並最大化將黃色跟紅色分別排序之後的 $\#\{{\sigma }_i^{\prime }=i\}$。

請構造一組解。

• 多筆測資、$\sum n\le 10^6$

先建 $i\to {\sigma }_i$ 的有向邊，此時圖會被分成許多個環。觀察到如果圖有兩個以上的連通塊，對各自分別排序就能將整個陣列排序。以下考慮圖只有一個連通塊的情況。

如果把環切成 $⟨i⟩,⟨j⟩$ 兩個部分：$i_1\to i_2\to \cdots \to i_k\to j_1\to j_2\to \cdots \to j_{n-k}\to i_1$，滿足 $i_1=1,j_1=2$，則可以發現：

• 選了位置 $i_p$ 會選到數字 $i_{p+1}$（選了位置 $i_k$ 會選到數字 $j_1=2$）。
• 選了位置 $j_q$ 會選到數字 $j_{q+1}$（選了位置 $j_{n-k}$ 會選到數字 $i_1=1$）。

因為 $1$ 跟 $2$ 比所有其他數字都還要小，所以把位置 $⟨i⟩$ 排序後只會讓 ${\sigma }_{i_1}^{\prime }=2$，${\sigma }_{i_p}^{\prime }=i_p$；把位置 $⟨j⟩$ 排序後只會讓 ${\sigma }_{j_1}^{\prime }=1$，${\sigma }_{j_q}^{\prime }=j_q$。

至此，就得到了排好 $n-2$ 個數字的方法，而顯然在只有一個環的情況下不存在排好恰 $n-1$ 或 $n$ 個數字的方法。

Problem K. Knocker

Tags: dp

給定正整數陣列 $⟨a⟩$，你可以選擇若干數字 $p_1,p_2,\dots ,p_k$ 並令 $a_i^{\prime }=((a_i\mathrm{mod}{p}_1)\mathrm{mod}{p}_2)\cdots \mathrm{mod}{p}_k$，請問有幾種可能的 $⟨a^{\prime }⟩$？

模 $998244353$ 輸出。

• $n\le 500$、$a_i\le 500$

• $\text{Claim 1.}$ 每次的 $\mathrm{mod}$ 操作必定可以取 $p>\lfloor \max (a_i)/2\rfloor$。

上述 Claim 1 的最大用處是把取 $\mathrm{mod}$ 操作變成減法操作，注意對一個數字「減法」之後他會變成不到一半。

• $\text{Claim 2.}$ 對每個合法的狀態都存在一種每個數字只被「減法」影響到至多一次的方案。

將陣列降序排序後，就可以來嘗試 DP 了：狀態 $\text{dp}[i][v]$ 代表 $a_i$ 是第一個沒有被「減法」的數字，且當前（為了不二次影響前面的數字）能取的 $p$ 下界是 $v$ 的陣列數量。

轉移採用遞推，枚舉合法的 $p$ 作為轉移，維護會被影響到的數字（$a_j<p$ 的最小 $j$），再拿滿足轉移條件的狀態 $\text{dp}[i][w{]}_{w\le p}$ 去更新 $\text{dp}[j][\max (w,a_i-p+1)]$。

時間複雜度：$\mathcal{O}(n{C}^2)$。

轉移應該可以用前綴和壓掉一個 $\mathcal{O}(C)$，待補。

Problem L. Lalo's Lawyer Lost

待補

給定一棵 $2n$ 個點的仙人掌，定義 $d(u,v)$ 是兩點的最短距離，請將這些點分成 $n$ 個 pair，使得 $\sum d(u_i,v_i)$ 最大。

• 多筆測資、$\sum n\le 100000$、$\sum m\le 400000$

The 3rd Universal Cup. Stage 8: Cangqian

• 連結：https://qoj.ac/contest/1780
• 時間：2025 Apr 2, 07:00-12:00
• 團隊：SorahISA
• 成績：5 / 13, Penalty 596, dirt 44% ( A B C D E F G H I J K L M )

在 A 大坐牢，寫了 python 不知道為什麼會 RE 卡了一個小時。

Problem A. Bingo

待補

Problem B. Simulated Universe

待補

Problem C. Challenge NPC

Tags: constructive

構造一張簡單無向圖 $G$ 使得存在一個正整數 $c$ 滿足最小點著色數 $\le c$ 且 greedy 解至少要用 $c+k$ 個顏色。

• Greedy 解：對 $i=1,2,\dots ,n$，將點 $i$ 著 $\mathrm{mex}\{c_u:u<i\wedge (u,i)\in E(G)\}$ 的顏色（此處的 $\mathrm{mex}$ 為 $1$-based）。

• $k\le 500$、$n\le 1024$

$k$ 這麼大，感覺就可以弄一張二分圖做到 $2$ 跟 $n/2$，所以就做完了。

只要把第 $k$ 小的奇數／偶數連向第 $1,2,\dots ,k-1$ 小的偶數／奇數就可以了。

• 因為是二分圖，所以最佳解顯然是 $2$。
• 第 $k$ 小的奇數／偶數會被 greedy 解填上顏色 $k$。

Problem D. Puzzle: Easy as Scrabble

待補

Problem E. Team Arrangement

Tags: greedy, bit operation

要把 $n$ 個人分成若干組，第 $i$ 個人希望自己在的小組有 $[{\ell }_i,r_i]$ 個人。如果一種分組方法每一組分別有 $c_1,c_2,\dots ,c_k$ 個人，那麼總價值就是 $\sum _{j=1}^k{w}_{c_j}$。

請求出最大價值的分組，或判斷其不可能達成。

• $n\le 60$、$|w_i|\le 10^7$

第一直覺是先枚舉每一組的大小，再判斷該分組能不能被達成。$n$ 個人的分組數量是 $p(n)$，而 $p(60)=966467$，於是大概要一個 $\mathcal{O}(n)$ 的方法來判斷。

最簡單的方法是 greedy：先將區間們依照右界小到大排序，再每次取 ${\ell }_i$ 的 lower bound 出來。用 multiset 果不其然的吃了 TLE，改成 map 之後有稍微改善，但複雜度仍然有一個 $\log n$。

注意到這題 $n\le 60$，每一組的大小也只有 $60$ 以下，可以用一個 uint64_t 來儲存！

• 跟用 map 的做法一樣，存在 $x$ $⟺$ (val >> x) & 1。
• 求 $\ell$ 的 lower bound 可以用 __builtin_ctzll(val >> l << l) 來做，這樣就可以在 $\mathcal{O}(1)$ 的時間內找到。
  • 注意 __builtin_ctzll(0) 會是 undefined behavior，可以特判，或是一開始就放 1 << (n+1) 進 val 裡面。

於是這樣的複雜度就變成 $\mathcal{O}(p(n)\cdot n^2/w)=\mathcal{O}(p(n)\cdot n)$ 了。

Problem F. Stage: Agausscrab

水題，跳過

Problem G. Crawling on a Tree

待補

Problem H. Permutation

待補

Problem I. Piggy Sort

待補

Problem J. Even or Odd Spanning Tree

Tags: mst, lca

給一張帶正邊權的 $n$ 點 $m$ 邊無向圖 $G$，求 weight 分別是奇數跟偶數的最小生成樹，輸出 weight 即可（不存在則輸出 $-1$）。

• 多筆測資、$\sum n\le 200000$、$\sum m\le 500000$

顯然有一邊的答案就是 MST 本身。

• $\text{Claim 1.}$ 令 $f(k)$ 是選了 $k$ 條奇邊的最小生成樹 weight，如果最小生成樹選了 $a$ 條奇邊，那答案一定是 $f(a-1)$ 或 $f(a+1)$。

• $\text{Claim 2.}$ 要得到 $f(a\pm 1)$ 只要枚舉樹外邊 $(u,v)$ 跟 $u⇝v$ 路徑上奇偶性相異的最大值換就好。

於是只要用 LCA 維護路徑上的奇數 weight、偶數 weight 最大值是多少就可以了。

時間複雜度：$\mathcal{O}(m\log n)$。

Problem K. Sugar Sweet 3

待補

Problem L. Challenge Matrix Multiplicatio

待補

Problem M. Triangles

待補

The 3rd Universal Cup. Stage 14: Harbin

• 連結：https://qoj.ac/contest/1817
• 時間：2024 Oct 27, 02:00-07:00
• 團隊：ネクロマンサー (SorahISA)
• 成績：6 / 13, Penalty 774, dirt 0% ( A B C D E F G H I J K L M )

沒看計分板以為 I 是水題就 AC 了，結果看了記分板之後才發現是測資太爛 + 自己不會估複雜度！？

A. Build a Computer

Tags:

請構造一個至多 $100$ 個點的自動機，該自動機需要且只能 accept $[L,R]$ 間數字沒有前導零的二進位表示法。

• 舉例來說，當 $(L,R)=(3,5)$ 時，自動機需要且只能接受 $11,100,101$ 這三個字串。

• $1\le L\le R\le 10^6$，你構造的圖只能有一個起點和一個終點，且不能有環

待補

B. Concave Hull

Tags: convex hull

給定 $n$ 個點，求其所有不是 convex 的 simple polygon 的最大面積 $\times 2$。

• 多筆測資、$\sum n\le 200000$、$|x_i|,|y_i|\le 10^9$、沒有三點共線

待補

C. Giving Directions in Harbin

水題，跳過

D. A Simple String Problem

Tags:

題目

• 測資

待補

E. Marble Race

Tags:

題目

• 測資

待補

F. 1D Galaxy

Tags:

題目

• 測資

待補

G. Welcome to Join the Online Meeting!

Tags:

題目

• 測資

待補

H. Subsequence Counting

Tags:

題目

• 測資

待補

I. A Brand New Geometric Problem

Tags:

題目

• 測資

待補

J. New Energy Vehicle

Tags: greedy

你在一維數線上開車，出發點是座標 $0$，有 $n$ 個油箱分別能裝 $a_1,\dots ,a_n$ 公升的油。有 $m$ 個加油站，第 $j$ 個加油站在座標 $x_j$ 處，並能夠幫你加滿第 $t_j$ 個油箱。你的車每行駛 $1$ 單位距離需要消耗 $1$ 公升的油，問最遠可以開到哪裡（用完油剛好到加油站也可以加油並繼續行駛）。

• 多筆測資、$\sum n\le 200000$、$\sum m\le 200000$、$a_i,x_j\le 10^9$

待補

K. Farm Management

Tags:

給定 $n$ 個工作 $({\ell }_i,r_i,w_i)$ 跟時間 $m$，請找到一個 schedule $⟨t⟩$ 使得

• ${\sum }_{i=1}^n{t}_i=m$ 且 $t_i$ 是整數
• ${\ell }_i\le t_i\le r_i$
• ${\sum }_{i=1}^n{w}_i\cdot t_i$ 收益最大

你可以將至多一個工作修改成 $(0,m,w_i)$，求收益最大值。

• $n\le 10^5$、$m\le 10^{11}$、$w_i\le 10^6$、${\ell }_i\le r_i\le 10^6$、$\sum {\ell }_i\le m\le \sum r_i$

待補

L. A Game On Tree

Tags:

題目

• 測資

待補

M. Weird Ceiling

Tags: math

求

$$\sum _{i=1}^n\frac{n}{\max \{k:k\le i\wedge n\mathrm{mod}k=0\}}$$

• 測資數量 $\le 1000$、$n\le 10^9$

$\mathcal{O}(\sqrt{n})$ 枚舉因數即可。

The 3rd Universal Cup. Stage 16: Nanjing

• 連結：https://qoj.ac/contest/1828
• 時間：2024 Nov 10, 02:00-07:00
• 團隊：ネクロマンサー (SorahISA)
• 成績：4 / 13, Penalty 565, dirt 0% ( A B C D E F G H I J K L M )

這場打的太混了 QwQ

整場都沒看計分板，因此一直覺得 L 可做，還有漏掉 G 是二元樹的性質。

Problem A. Hey, Have You Seen My Kangaroo?

待補

Problem B. Birthday Gift

Tags: observation

給定只包含 012 的字串 $s$，你可以不斷刪除 不為 01 或 10 的 substring，問字串最短長度。

• 多筆測資、$\sum |s|\le 500000$

先考慮只有 01 的做法：可以 greedy 的遇到相同字元就刪掉（用 stack 維護）。

在這題也可以用類似的方法，維護把相鄰 00 跟 11 刪去的字串，會得到被 2 切開來，每段都是 01 交錯的字串。

而這就可以使用 DP，維護以 0 跟 1 結尾的字串的所有長度，遇到 2 就將其換成 0 或 1（一樣當遇到連續相同字元就刪掉），因為可以構造出來的長度是連續的，於是可以只維護最小最大值。具體實作可以參考 submission。

以下是題解給出的天才解法：

令 $S^{\prime }$ 為把 $S$ 所有偶數 position 的 01 字元反轉形成的字串，那 $S$ 中刪掉 00 或 11 就會變成 $S^{\prime }$ 中刪掉 01 或 10。

一樣先假設沒有 2 的情形，可以發現只有當 $S^{\prime }$ 字串全部字元相同時才不存在 01 或 10，因此答案就是 $S^{\prime }$ 中 0 跟 1 的數量差。

如今我們只在意數量差了，那麼自然有 2 就可以往數量少的那邊補，這份 code 只有短短 8 行。

Problem C. Topology

待補

Problem D. Toe-Tac-Tics

待補

Problem E. Left Shifting 3

水題，跳過

Problem F. Subway

待補

Problem G. Binary Tree

Tags: interactive

待補

Problem H. Border Jump 2

待補

Problem I. Bingo

Tags: inclusive-exclusive, ntt

給你 $a_1,a_2,\dots ,a_{nm}$，你要將其由左上至右下填入 $n\times m$ 的表格 $G$ 中。定義一個表格的 bingo 數 是

$$\min \left(\underset{1\le r\le n}{\min }\left(\underset{1\le c\le m}{\max }{G}_{r,c}\right),\underset{1\le c\le m}{\min }\left(\underset{1\le r\le n}{\max }{G}_{r,c}\right)\right)$$

請計算所有 $(nm)!$ 種 $a$ 的排列的 bingo 數之和，模 $998244353$。

• $n\cdot m\le 200000$

min of max 很不好算，能不能把他換成只有 max 呢？

答案是可以的！用 min-max 排容：

$$\underset{x\in S}{\min }x=\sum _{\varnothing ⊊T\subseteq S}(-1{)}^{|T|+1}\underset{y\in T}{\max }y$$

以上算式的感性證明就是當 max 是第 $k$ 小的時候你有 $2^{k-1}$ 種其他東西的取法，而這些除了在 $k=1$ 的時候都會正負消掉。

固定 $a_p$ 為 $\max T$，並枚舉 $T$ 中包含了幾個 row max、幾個 column max，可以得到以下算式：

$$\sum _{p=1}^{nm}{a}_p\sum _{r=1}^n\sum _{c=1}^m(-1{)}^{r+c+1}(\genfrac{}{}{0ex}{}{n}{r}\left)\right(\genfrac{}{}{0ex}{}{m}{c}\left)\right(\genfrac{}{}{0ex}{}{p-1}{k-1})k!(nm-k)!(\text{where }k=rm+cn-rc)$$

其中 $k$ 代表的是被 $T$ 裡的 row 跟 column 覆蓋的格子數量，max of max 讓我們只需要計算這 $k$ 個格子的 max 恰好是 $a_p$ 的排列數量就好。

直接做是 $\mathcal{O}(n^2{m}^2)$，得想辦法加速。令

$$f_k=\sum _{p=1}^{nm}{a}_p\cdot \left(\genfrac{}{}{0ex}{}{p-1}{k-1}\right)\cdot k!\cdot (nm-k)!$$

那麼答案就是

$$\sum _{r=1}^n\sum _{c=1}^m(-1{)}^{r+c+1}(\genfrac{}{}{0ex}{}{n}{r}\left)\right(\genfrac{}{}{0ex}{}{m}{c})\cdot f_k(\text{where }k=rm+cn-rc)$$

把二項式拆開，$f_k$ 可以整理成如下形式，注意下標從 $k$ 開始：

$$f_k=\sum _{p=k}^{nm}\frac{a_p\cdot (p-1)!\cdot k\cdot (nm-k)!}{(p-k)!}$$

把只跟 $k$ 有關的提出來變成 $z_k$，剩下的式子能整理成 $f_k=z_k\cdot {\sum }_{p=k}^{nm}{x}_p\cdot y_{p-k}$ 的形式，感覺跟卷積很像了？

• $x_p=a_p\cdot (p-1)!$
• $y_{p-k}=(p-k){!}^{-1}$
• $z_k=k\cdot (nm-k)!$

$⟨x⟩,⟨y⟩,⟨z⟩$ 都是能預處理的，於是我們將 $⟨x⟩$ 先 reverse 讓 $\sum$ 裡面變成 $x_{nm-p}\cdot y_{p-k}$ 的形式，讓 $f_k=z_k\cdot (x\ast y{)}_{nm-k}$，這題就能開心的用 NTT 解決掉了！

時間複雜度：$\mathcal{O}(nm\log (nm))$。

Problem J. Social Media

Tags: N/A

水題，跳過

Problem K. Strips

Tags: greedy

水題，跳過

Problem L. $P\oplus Q=R$

待補

Problem M. Ordainer of Inexorable Judgment

待補

The 3rd Universal Cup. Stage 28: Haidian Huangzhuang

• 連結：https://qoj.ac/contest/1903
• 時間：2025 Feb 2, 02:00-07:00
• 團隊：ネクロマンサー (SorahISA)
• 成績：0 / 11, Penalty 0, dirt 0% ( A B C D E F G H I J K )

感冒所以只打快三個小時，但一題都沒做出來

Problem A. Iron Warrior

Problem B. Little, Cyan, Fish!

Problem C. Currency

Tags: min-cut

有一張 $2\times n$ 個點的網格圖，點的編號為 $(i,j)$（$1\le i\le 2$、$1\le j\le n$），且 $(i,j)$ 跟 $(i^{\prime },j^{\prime })$ 之間有一條帶正權無向邊當且僅當 $|i-i^{\prime }|+|j-j^{\prime }|=1$。

接著有 $m$ 個限制 $(i,j,c)$，表示若同時走了 $(1,i)\to (1,i+1)$ 跟 $(2,j)\to (2,j+1)$ 兩條邊，則需要花費額外代價 $c$。

請求出從 $(1,1)$ 走到 $(2,n)$ 的最小代價。

• $n\le 500$、$m\le 1000$、$1\le$ 權重 $\le 10^9$

網路流最小割經典題。

首先，對每個 $i$，$(1,i)\to (1,i+1)$ 跟 $(2,i)\to (2,i+1)$ 只會走其中恰好一個，否則路徑必然出現環。

因此，對 $(\ast ,i)\to (\ast ,i+1)$ 的邊建立一個點 $i$。令走上方為 $\mathbf{A}$、走下方為 $\mathbf{B}$，則可以建立 $\mathbf{A}\to i$ 跟 $i\to \mathbf{B}$ 的邊並求出 $\mathcal{C}=\min \mathrm{cut}(\mathbf{A},\mathbf{B})$。如果割掉 $\mathcal{C}$ 之後 $i$ 跟 $\mathbf{A}$ 相連，則代表 $(1,i)\to (1,i+1)$ 這條邊被選擇，反之亦然。

權重的設定也很簡單，$\mathbf{A}\to i$ 的權重就是下方該條邊的權重，$i\to \mathbf{B}$ 的權重就是上方該條邊的權重。會走直線 $(1,i)\leftrightarrow (2,i)$ 的情況只會發生在 $i$ 跟 $i+1$ 不同邊（被切開了），於是可以在 $i\leftrightarrow i+1$ 雙向的建一條邊，權重就是直走邊的權重。不過要注意的是，可能會發生第一條邊走下面或最後一條邊走上面的情況，於是需要將方格左右各拓寬一格，讓 $\mathbf{A}\to 0$ 跟 $n\to \mathbf{B}$ 的權重設為 $\infty$。

最後的 $m$ 個限制，只要建立 $i\to j$ 權重為 $c$ 的單向邊即可。該權重只有在 $i$ 連著 $\mathbf{A}$ 且 $j$ 連著 $\mathbf{B}$ 時才會被計算進去。

於是把 Dinic 模板貼上、按上所述的建好邊、跑 $\mathbf{A}\to \mathbf{B}$ 的最大流即可。

Problem D. Widely Known Problem

Problem E. Light Drinking and Low Singing

Problem F. Trash Problem

Problem G. Analysis

Problem H. Algebra

Problem I. Twenty-two

Problem J. Loving You in My Humble Way

Problem K. Ying's Cup

2025 ICPC Asia Pacific Championship

• 連結：https://codeforces.com/contest/2073
• 時間：2025 Mar 1, 10:00-15:00
• 團隊：NYCU_MyGO!!! (SorahISA, ub33, nella17)
• 成績：7 / 13, Penalty 1025, dirt 50% ( A B C D E F G H I J K L M )

A. Control Towers

Tags: math

給一個 $n\times m$ 的 grid，有些格子不能放置控制塔，請問有多少種放置四座相異控制塔的方法滿足以下條件：

• 編號 $i$ 跟 $i+1$ 的控制塔需要在同一行或同一列（$i=1,2,3$）。

• $1\le n,m\le 2000$

解法

B. Three-Dimensional Embedding

Tags:

待補

解法

C. Cactus Connectivity

Tags:

待補

解法

D. Tower of Hanoi

Tags:

待補

解法

E. Minus Operator

Tags:

待補

解法

F. Hold the Star

Tags:

待補

解法

G. Corrupted File

Tags: greedy

給定 $\text{01}$-字串 $S$，你可以不斷地選擇相鄰兩個字元合併成一個，合併後的結果是 $\text{AND}$ 操作的值。請問有沒有辦法變成字串 $T$？

• 多筆測資、$|T|\le |S|$、$\sum |S|\le 100000$

首先可以觀察到 $T$ 中的 $\text{1}$ 只能是 $S$ 中的 $\text{1+}$、$\text{0}$ 只能是 $S$ 中的 $\text{.}\star \text{0.}\star$。

將 $S$ 跟 $T$ 以 $\text{0}$ 切開後整理成「每段連續 $\text{1}$ 的長度」的形式（舉例來說：$\text{00111011011}$ 會變成 $[0,0,3,2,2]$），以下稱之為 $V_S$ 跟 $V_T$。

有幾個邊界 case 需要注意：

1. $|V_T|$ 不能超過 $|V_S|$，因為每個 $T$ 的 $\text{0}$ 至少要吃掉一個 $S$ 的 $\text{0}$。
2. $V_T[0]\le V_S[0]$ 且 $V_T[-1]\le V_S[-1]$，因為 $T$ 中第一段的 $V_T[0]$ 個 $\text{1}$ 只能對上 $S$ 的前面 $V_S[0]$ 個 $\text{1}$（$\text{1}$ 吃不掉 $\text{0}$），最後一段同理。

接著就可以貪心的對 $i=1,2,\dots ,|V_T|-2$ 找 $V_S$ 中 $\ge V_T[i]$ 的第一個位置。

• 可以 greedy 匹配的原因是 $T$ 中連續的 $\text{1}$ 只會匹配到 $S$ 中連續的 $\text{1}$，且對 $i<j$，$T_i$ 匹配到的位置一定在 $T_j$ 匹配到的位置之前。
• 也就是說要找到任意 $1\le i_1<i_2<\cdots <i_{|V_T|-2}\le |V_S|-2$ 滿足 $\forall k.V_T[k]\le V_S[i_k]$，是經典的 greedy 問題。

H. Secret Lilies and Roses

Tags: interactive, binary search

有一個隱藏的長度 $n$ 的字串 $S$，其中只包含 $\text{L}$ 跟 $\text{R}$ 兩種字元。請在 $Q$ 次詢問以內找到一個位置 $p\in [0,n]$ 滿足：

• 在 $S_1,S_2,\dots ,S_p$ 中的 $\text{L}$ 數量（$={\ell }_p$）等於在 $S_{p+1},S_{p+2},\dots ,S_n$ 中的 $\text{R}$ 數量（$=r_p$）。

你有兩種詢問操作可以做，分別是：

1. 給定 $p\in [1,n]$，詢問 $S_p$。
2. 給定 $p\in [0,n]$，詢問 $m_p{=}_{\text{def}}{\ell }_p\times r_p$。

• 多筆測資、$n\le 100$、$Q=10$

先觀察到 $c_p{=}_{\text{def}}{r}_p-{\ell }_p$ 在 $p=0$ 時會是 $S$ 中 $\text{R}$ 的數量，且 $c_{p+1}=c_p-1$（因為一定是多一個 $\text{L}$ 或少一個 $\text{R}$）。目標 $c_p=0$ 的位置就剛好是 $p=\#\text{R}$。

如果能戳到第一個 $\text{L}$ 或最後一個 $\text{R}$ 得到他的 multi，就能直接知道某個 $p$ 的 $c_p$。

觀察 $m_p$ 的性質：他會有一個前綴後綴是 $0$、中間（可能為空）都是非 $0$。

為了得到 $0$ 跟非 $0$ 的交界，我們可以嘗試搜出一個 $\text{RL}$ substring，令 $\text{R}$ 的位置為 $p^{\ast }$，則

• ${\ell }_{p^{\ast }+1}$ 戳在 $\text{L}$ 右邊所以是 ${\ell }_{p^{\ast }}+1$，$m_{p^{\ast }+1}=m_{p^{\ast }}+r_{p^{\ast }}$；
• $r_{p^{\ast }-1}$ 戳在 $\text{R}$ 左邊所以是 $r_{p^{\ast }}+1$，$m_{p^{\ast }-1}=m_{p^{\ast }}+{\ell }_{p^{\ast }}$。

而要在陣列中搜出 $\text{RL}$ substring 是經典題（DOMJudge 測機題），可以用二分搜來做。假設 $S_0=\text{R}$、$S_{n+1}=\text{L}$，則可以二分搜尋 $p$ 並更新左右界滿足區間是 $\text{R}\dots \text{L}$。

注意特判搜到的 $p^{\ast }$ 是 $0$ 或 $n$ 的情況。

詢問次數是二分搜的 $\lceil {\log }_{2}n\rceil =7$ 加上詢問 $m_{p^{\ast }\pm 1}$ 的 $3$ 次，總計 $10$ 次詢問。

I. Squares on Grid Lines

Tags:

待補

解法

J. Gathering Sharks

Tags: dp

待補

經典區間 DP。

令 $\text{dp}[\ell ][r]$ 表示把編號 $[\ell ,r]$ 的人都移到編號 $\ell$ 的位置的最小代價。則有轉移式：

$$\text{dp}[\ell ][r]=\underset{\ell \le m<r}{\min }\left(\text{dp}[\ell ][m]+\text{dp}[m+1][r]+|{\text{pos}}_{\ell }-{\text{pos}}_{m+1}|\right)$$

按長度由小至大 DP 即可。

K. Book Sorting

Tags:

待補

解法

L. Boarding Queue

Tags: N/A

待補

對所有相鄰兩人 $(a,b)$ 檢查：如果 $a\le p$ 代表 $p$ 會走到 $a$ 的位置，面對的是 $b+p-a$，判斷該數字有沒有在 $[1,n]$ 即可。

M. Can You Reach There?

Tags:

待補

解法

2020 ICPC Asia Jakarta Regional Programming Contest

• 連結：https://qoj.ac/contest/1019
• 時間：2025 Mar 10, 12:00-17:00
• 團隊：SorahISA
• 成績：8 / 13, Penalty 1158, dirt 20% ( A B C D E F G H I J K L M )

4:03 過了 I 才第一次看計分板，發現 I 竟然場內滅台，場外也只有三隊 AC！？

A. Comic Binge

Tags:

meow

B. Moon and Sun

Tags:

meow

C. Cul-De-Sac Parades

Tags:

meow

D. Forbidden Card

Tags:

meow

E. Exchange Bottleneck

Tags:

meow

F. Shopping Changes

Tags:

meow

G. Permutation Transformation

Tags:

meow

H. Writing Tasks

Tags:

meow

I. Red Black Ball

Tags:

meow

J. Token Distance

Tags:

meow

K. Tree Beauty

Tags:

meow

L. Robust Defense

Tags:

meow

M. Police Stations

Tags:

meow

2024 ICPC Asia Seoul Regional Programming Contest

• 連結：https://www.acmicpc.net/category/detail/4348
• 時間：2024 Nov 17, 09:30-14:30
• 團隊：ネクロマンサー (SorahISA)
• 成績：4 / 12, Penalty 185, dirt 33% ( A B C D E F G H I J K L )

A. Bottles

Tags: prefix sum

有 $n$ 個人在比賽，編號為 $i$ 的人會在時間 $0$ 從區域 $1$ 出發，在時間 ${\sum }_{k=1}^j{t}_{i,k}$ 抵達區域 $j+1$。

在不考慮整數點時間的情況下，請問每個區域最多同時有多少人？

• $n\le 100$、$m\le 300$、$t_{i,j}\le 10000$

水題，跳過

B. Cards Flipping

Tags: N/A

給定兩個長度 $n$ 的序列 $⟨a⟩,⟨b⟩$，請對每個 $i$ 選擇 $c_i:=a_i$ 或 $c_i:=b_i$ 使得 $|\{c_i\}|$ 最大。

• $n\le 200000$、$0\le a_i,b_i\le 1000000$

建圖，建了 $(a_i,b_i)$ 的邊之後相當於是要對每條邊選周圍的一個點。

觀察到如果一個大小為 $k$ 的連通塊是樹，那麼隨意定根並讓所有邊選擇較低的點就能做到 $k-1$。

如果該連通塊有至少 $k$ 條邊，那麼可以把邊拔到剩下 $k$ 條變成基環樹，讓環上的邊互指，樹上的邊往下指就能做到 $k$。

用 DSU 維護連通塊大小以及邊的數量即可，時間複雜度 $\mathcal{O}(n\alpha (n))$。

C. Colorful Quadrants

Tags:

meow

• meow

待補

D. Ladder Update

Tags:

meow

• meow

待補

E. Mausoleum

Tags:

meow

• meow

待補

F. Pair Sorting

Tags:

meow

• meow

待補

G. Palindromic Length

Tags:

meow

• meow

待補

H. Protecting Kingdom

Tags:

meow

• meow

待補

I. Square Stamping

Tags:

meow

• meow

待補

J. Street Development

Tags:

meow

• meow

待補

K. String Rank

Tags:

meow

• meow

待補

L. Triangle

Tags: N/A

給定一個頂點都在整數點的三角形 $△ABC$，請求出在三條邊 $\overline{AB},\overline{BC},\overline{CA}$ 上各選一個整數點（不含頂點）圍成三角形的最大面積 $S_{\text{max}}$ 以及最小面積 $S_{\text{min}}$。

輸出 $2\cdot S_{\text{max}},2\cdot S_{\text{min}}$ 即可，如果無解請輸出 $-1$。

• $|$ 座標 $|$ $\le 10^9$

顯然最大面積就是三角形的面積，但不能取頂點，所以要想辦法取盡量靠近的點；最小面積就是三條邊的中點連線，但中點不一定是整數點，所以要找到最接近的整數點。

$\overline{AB}$ 上的所有點會是 $\left(A_x+k\cdot \frac{B_x-A_x}{d},A_y+k\cdot \frac{B_y-A_y}{d}\right)$ 的形式（其中 $0\le k\le d$ 且 $k,d$ 都是整數），而要滿足他是整數點就必須滿足 $d\mid (B_x-A_x)$ 且 $d\mid (B_y-A_y)$，所以取 $d=\gcd (B_x-A_x,B_y-A_y)$。

於是就可以在三條邊上分別取 $k=1,\lfloor d/2\rfloor ,\lceil d/2\rceil ,d-1$ 四個點計算三角形面積即可。

時間複雜度 $\mathcal{O}(4^3)$。

2024 ICPC Asia Taichung Regional Programming Contest

• 連結：https://codeforces.com/contest/2041
• 時間：2024 Nov 17, 09:30-14:30
• 團隊：NYCU_MyGO!!! (SorahISA, ub33, nella17)
• 成績：10 / 14, Penalty 874, dirt 9% ( A B C D E F G H I J K L M N )

A. The Bento Box Adventure

Tags: N/A

輸入四個 $1\sim 5$ 之間的相異正整數 $a,b,c,d$，請判斷 $1\sim 5$ 哪個數字沒出現過

• $1\le a,b,c,d\le 5$

輸出 $15-(a+b+c+d)$ 即可。

B. Bowling Frame

Tags: N/A

有 $w$ 個白色瓶子跟 $b$ 個黑色瓶子。你要排成 $n$ 排，滿足第 $i$ 排有 $i$ 個相同顏色的瓶子，請求出 $n$ 的最大值。

• 測資數量 $\le 100$、$0\le w,b\le 10^9$

待補

C. Cube

Tags: bitmask dp

找到三個 $1,2,\dots ,n$ 的排列 $⟨x⟩,⟨y⟩,⟨z⟩$ 使 $\sum A_{x_i,y_i,z_i}$ 最大。

輸出該最大值就好。

• $n\le 12$、$0\le A_{x,y,z}\le 2\cdot 10^7$

待補

D. Drunken Maze

Tags: bfs

給定一個 $n\times m$ 的矩陣，其中恰有一個起點跟一個終點，且有些位置是不能行走的牆壁。你每次可以朝著四方位相鄰的格子移動一步，但是你不能連續四步走同樣的方向，請求出起點到終點的最短路徑長度（不存在則輸出 $-1$）。

• $n,m\le 10000$、$nm\le 200000$、邊界都是牆壁

一樣用 BFS 紀錄最短路即可，但狀態要多兩個維度紀錄走了哪個方向（大小為 $4$）跟走了幾步（大小為 $4$）。

• $\text{dis}[r][c][d][s]$ 代表抵達 $(r,c)$ 且此前 $s$ 步的方向都是 $d$ 的最短路徑長度。

只要從 queue 裡面 pop 出 $(r_t,c_t,\ast ,\ast )$ 就能直接輸出答案。

時間複雜度：$\mathcal{O}(nm\cdot 4\cdot 4)$。

E. Beautiful Array

Tags: N/A

請構造一個長度介於 $[1,1000]$、數值界於 $[-10^6,10^6]$ 的整數陣列滿足其平均值為 $a$ 且中位數為 $b$。

• $|a|,|b|\le 100$

輸出 $-1000-b$、$b$、$1000+3a$ 即可。

F. Segmentation Folds

Tags: top-down dp, prime sieve

有一個區間 $[\ell ,r]$ 跟兩種摺疊操作 $\text{LTR}$、$\text{RTL}$：

• $\text{LTR}$：選擇最大的 $x$ 滿足 $\ell <x\le r$ 且 $\ell +x$ 是質數，並將區間縮小為 $[(\ell +x)/2,r]$。
• $\text{RTL}$：選擇最小的 $x$ 滿足 $\ell \le x<r$ 且 $r+x$ 是質數，並將區間縮小為 $[\ell ,(r+x)/2]$。

請輸出有幾種摺疊操作的序列可以使最後的區間長度最小。請輸出答案模 $998244353$ 的值。

• 測資數量 $\le 10$、$1\le \ell <r\le 10^{12}$、$r-\ell \le 100000$

觀察到新的端點 $\frac{\ell +x}{2}$ 或 $\frac{r+x}{2}$ 乘以 $2$ 之後是質數，於是問題可以被變化為以下模樣：

• 初始區間是 $[2\ell ,2r]$。
• $\text{LTR}$：選擇 $\le \frac{\ell +r}{2}$ 的最大質數當作新的 $\ell$。
• $\text{RTL}$：選擇 $\ge \frac{\ell +r}{2}$ 的最小質數當作新的 $r$。

於是可以先篩出區間 $[2\ell +1,2r-1]$ 內的質數。由於每個合數 $a$ 必定有一個 $\le \sqrt{a}$ 的質因數，所以透過預處理 $\sqrt{2C}$ 以下的質數再對區間進行篩選（就跟一般質數篩很像，除了左界要調整到第一個 $>p$ 的 $p$ 的倍數），就能在 $\mathcal{O}((r-\ell )\ln (r-\ell ))$ 時間篩出區間內所有質數。

考慮直接對其進行 top-down 的 DP。質數數量每一 fold 大約會變成一半，於是複雜度大約是 $\mathcal{O}(r-\ell )$。

還不會好好證明複雜度，待補。

G. Grid Game

Tags: vbcc, implementation

有一個 $n\times n$ 的白色棋盤，其中有 $q$ 個垂直的長條被塗成黑色的，保證白色的區塊四方位連通。請求出有多少個位置滿足該位置被塗黑之後白色的區塊不再四方位連通。

• 測資數量 $\le 125$、$n\le 10^9$、$\sum q\le 100000$

假設所有格子都被建出來，那麼直接在上面找割點就是答案了。不過本題的格子數量太多，所以要想辦法減少重要點的數量。

待補

H. Sheet Music

Tags: math

定義兩個長度皆為 $n$ 個序列 $⟨a⟩,⟨b⟩$ 本質相同，若且惟若對所有 $1\le i\le n-1$ 皆有以下其中一種情況成立：

• $a_i<a_{i+1}$ 且 $b_i<b_{i+1}$
• $a_i=a_{i+1}$ 且 $b_i=b_{i+1}$
• $a_i>a_{i+1}$ 且 $b_i>b_{i+1}$

請問有多少個本質不同、長度為 $n$、且每個元素都是 $[1,k]$ 之間的正整數序列？

請輸出答案模 $998244353$。

• $n\le 10^6$、$k\le 10^9$

先假設沒有 $k$ 的限制，那麼答案就是 $3^{n-1}$。

再假設沒有 $=$ 的狀況，那麼合法的序列就是所有沒有連續 $k$ 個 $>$ 或 $<$ 的序列，這個序列的數量可以透過 DP 求得。

$$f_{\ell }=\sum _{i=1}^{\min (k-1,\ell )}{f}_{\ell -i}$$

初始狀態為 $f_0=2$、目標答案就是 $f_{n-1}$，可以用前綴和 $\mathcal{O}(n)$ 計算。

現在考慮多出 $=$。顯然 $=$ 可以放在任何地方，所以如果有 $e$ 個 $=$，那麼答案就是 $f_{n-1-e}\cdot \left(\genfrac{}{}{0ex}{}{n-1}{e}\right)$。

$$ans=\left(\sum _{e=0}^{n-1}{f}_{n-1-e}\cdot \left(\genfrac{}{}{0ex}{}{n-1}{e}\right)\right)-1$$

時間複雜度：$\mathcal{O}(n)$。

I. Auto Complete

Tags: trie

meow

• meow

待補

J. Bottle Arrangement

Tags:

給定 $⟨a⟩,⟨b⟩$，你可以將 $⟨b⟩$ 的若干位置減一並將整個 $⟨b⟩$ 重新排序，使得

• $b_1\le \cdots \ge b_n$（$b$ 是 bitonic sequence）
• $b_i<a_i$ for all $1\le i\le n$

請輸出最少要對多少位置減一，如果全部都減一仍不可能達成，則輸出 $-1$。

• $n\le 500000$、$1\le a_i,b_i\le 10^9$、$⟨b⟩$ 全部元素皆相異