## 第二屆 Chi 怪壓常比賽 題解

## 比賽結果


## 題解

### A

紀錄每個數字第一次的位置，那答案就是(第二次-第一次)的加總，掃過去 $O(n)$。

### B

折半枚舉 (meet in the middle) 所有可能，分成左右邊兩堆 (各 2^{n/2} 個數)，排序好右邊的數，接著窮舉左邊的數對右邊做二分搜找邊界，時間複雜度 $O(2^{n/2}n)$

### C

這題因為沒辦法防作弊，不好管理所以沒搬上去

題目敘述: https://zerojudge.tw/ShowProblem?problemid=o295 (需要登入才能看到)

#### 性質

其實這題很像二分搜，假設我們確定答案在 $l \sim r$ 之間，尋找一個值假設叫 mid 如果回傳 ">= 答案" ，那代表答案 $l \sim mid$，否則為 $mid+1 \sim r$

#### 解法

我們可以用區間 dp，定義 $dp_{i,j} = k$ 代表知道答案在 $i \sim j$ 之間所需要的成本為 $k$，

好好列好轉移式，可以做到 $O(n^3)$

### D

解題說明 by M-SQRT

#### 前言

這題是 [k683. A+B Problem - Revisited](https://zerojudge.tw/ShowProblem?problemid=k683) 的延伸，建議先完成並熟悉作法再來思考這一題。

#### 性質

實作運算的關鍵在於要能夠容錯，觀察我們能夠使用的運算操作，其中的 $\text{AND, OR, SET}$ 都可以透過重複做一次運算，來確保運算有被執行到。它們都是對記憶體進行**修改**，而非造成一個**變化**，所以多執行一次相同的操作並不會造成計算錯誤。

#### 解題想法

剩餘無法保證能夠正確計算的部分，可以透過一種常見的容錯技術（$\text{TMR}$）來處理，其關鍵就是將需要執行的操作做三次，最後進行比對。題目保證只會被拿掉一行操作，所以三次計算一定至少有兩次得到正確結果。

我認為這是整題最精采的部分，您可以試著自行推導。
:::spoiler 如何從三個結果比對出正確的？
相信你馬上就發現了，少了條件的判斷方式，這個部分不太容易處理。

這裡我們將透過 $\text{AND, OR, SET}$ 這些可以透過執行兩次保證計算結果的操作來完成。

對於三個可能的答案 $A, B, C$，將其兩兩取交集（$\text{AND}$），得到 $AB, \color{#2ECC71}{AC}, BC$。
將 $AB, \color{#2ECC71}{AC}, BC$ 取聯集（$\text{OR}$），就是答案 $\text{ANS}$ 了。

對於一個 $1$ 位元，如果它是正確的（答案對應的位元也是 $1$），那在取交集時，會因為必定有兩個值是正確的，而至少被保留一份在 $AB, \color{#2ECC71}{AC}, BC$ 之中，這個位元會經過下一步的聯集，成為答案的一部份。
對於一個 $1$ 位元，如果它是錯誤的（答案對應的位元是 $0$），那在取交集時，會因為兩個正確的值並沒有那個 $1$ 位元，而完全不存在於 $AB, \color{#2ECC71}{AC}, BC$，三個值經過下一步的聯集，自然也不會存在這個 $1$ 位元。
:::

目前筆者首殺使用 $779$ 行完成，歡迎挑戰。

### E - 超級ㄌㄌ測試

#### 解法 1

我們可以觀察出，如果一個數被 xor 兩次，那會抵消，所以我們可以想像一個 bool 陣列 $b_{h,i,j}$ 代表陣列第 $h$ 列的第 $i$ 行這個元素，有沒有被最初列的第 $j$ 個元素 xor 過。直接計算是 $O(n^2 \times k)$，顯然不夠快，下個步驟是我們可以發現 $b_{h,i,j}$ 會等於 $b_{h,i+x,j+x}$ ($x$ 為整數)，所以我們可以把維度降到二維，只計算 $b_{h,0,j}$，之後再推論出其他的項。

具體作法會變成給一個二進數，定義 $b_0 = 1$

接著 $b_{i+1}$ = $b_{i}$ xor $(b_{i} << 1)$

如 $b_1 = 1\ xor\ 10 = 11$, $b_2 = 11\ xor\ 110 = 101$

因此我們就做到了 $O(nk)$。

但是 $k$ 大的感人，我們可以觀察這個序列 :

1
11
101
1111
10001
110011
1010101
11111111

這個是一個謝爾賓斯基三角形 (Sierpinski triangle)，可以發現他每 $2^i$ 在 $2^i$ 個前的位元會循環 (可以用數學歸納法證)

如下圖 :

1
11
101
1111

1000 1
1100 11
1010 101
1111 1111

所以如果只要考慮前 $2^i$ 個位元則 $b_k = b_{k-2^i}$ $(k-2^i \geq 0)$

因此我們只要算前面 $2^{\lceil log(n)\rceil}$ 的 $b$ 就可以了。

使用 bitset 可以做到 $O(\frac{n^2}{64})$，計算次數約等於 $2 \times 10^8$ ，足夠快通過。

#### 解法 2

從解題 1 前面的想法，$b_{i,j}$ (本來的 $b_{i,0,j}$ 省略 0 那維) 會是 $C^i_j\ (mod\ 2)$，可以使用盧卡斯定理 (Lucas's theorem)，以 $O(n\ lg\ n)$ 得出。

### F - 很多對對序列問題

#### 想法

如果我們已經知道對於 $n=k$ 的答案，那有沒有辦法推廣 $n=k+1$ 的呢？

如我們知道 $n = 1$ 的答案，可以想像 $n = 2$ 如下：

^1^1^

我們要在 ^ 的地方填入兩個2，填入會造成三個影響：

#### 1. 填入的方法數

首先如果不考慮插入的數會不會影響本來的索引值、以及新插入的數的索引值差，那第 $k+1$ 項的答案會是第 $k$ 項的 $(k+1)(2k+1)$ 倍，也就是插入的方法數，因為對於每一種排列插入的方法數都是一樣的。

#### 2. 插入的數自己的距離

和前面討論的一樣，我們討論每一種插入方式，那新插入的這對他們之間的距離

如果第一個數放最前面，枚舉第二個的位置，那總共會是 $(1+2+3+4+5+...+2k)$ 的距離

如果第一個數放第二個位置，那總共會是 $(1+2+3+4+5+...+2k-1)$ 的距離

以此類推，總共會是 $(1)+(1+2)+(1+2+3)+...+(1+2+3+...+2k) = \frac{(2k)(2k+1)(2k+2)}{6}$ 的距離

#### 3. 插入的數所帶來的影響

可以想成我們枚舉 $1 \sim k$ 的其中數，然後插入兩個 $k+1$，和前面一樣我們枚舉
這一對的數出現的位置，那會變成這樣 :

#### 總結

by 預處理一些東西，可以做到 $O(n)$。