對于 D 題的原題意已旧，出題人和驗題人賽前都沒有發(fā)現(xiàn)標算存在的問題策吠，導致了許多選手的疑惑和時間的浪費层皱，在此表示真誠的歉意伴箩！

預計難度分布：

Easy - DJKL, Medium - ABCEG, Hard - FHI

A. Integers Exhibition

不難發(fā)現(xiàn)非 K-magic 數(shù)是非常少的，考慮先預處理出來绝葡，二分回答詢問深碱。

以下我們討論如何求出非 K-magic 數(shù)，為方便描述藏畅，我們稱一個正整數(shù)是良好的當且僅當其是非 K-magic 的敷硅。

對于一個質(zhì)數(shù) p，我們考慮所有僅包含小于 p 的質(zhì)因子的正整數(shù)集 G愉阎。不難發(fā)現(xiàn)：

• 若 x \in G绞蹦，且在 G 中已經(jīng)有超過 K 個小于 x 的整數(shù)約數(shù)個數(shù)多于 x，即 x 一定不是良好的榜旦，則 x p ^ c (c \ge 0) 也一定不可能是良好的幽七。

這樣我們就可以得到一個初步的想法。開始我們認為僅有 1 是良好的溅呢，枚舉質(zhì)因子 p澡屡，對于每一個原來認為是良好的數(shù) x，將 x p ^ c (c \ge 0) 加入候選列表咐旧，接著將候選列表排序挪蹭，除去已經(jīng)可以確定不是良好的數(shù)，進入下一輪迭代休偶。容易證明梁厉，在這個算法中，篩去一個不是良好的數(shù) x踏兜，是不會在后續(xù)過程中令一個原本不是良好的數(shù)词顾，變成一個良好的數(shù)的，故篩去良好的數(shù)的過程是合法的剪枝碱妆。

然而枚舉的質(zhì)因子的范圍有多大呢肉盹？聯(lián)想 K = 0 這一經(jīng)典問題，我們知道對于 10 ^ {18} 的范圍疹尾，考慮前 20 個質(zhì)因子都綽綽有余了上忍，因為將更大的質(zhì)因子加入是非常不優(yōu)的。在 K 更大的時候纳本，我們采用“迭代至穩(wěn)定”的思想窍蓝，每一輪迭代后檢查答案是否變化，如果在較長一段迭代后答案無任何變化繁成，我們就認為質(zhì)因子 p 的上界已經(jīng)達到吓笙。經(jīng)過實踐，在 K = 233 時巾腕，p 的最大值取到 293 即可面睛。

我們考慮如何在一輪迭代中除去確定不是良好的數(shù)絮蒿。考慮維護前 K + 1 大值叁鉴，從小到大枚舉候選列表中的數(shù) x土涝，若 x 小于第 K + 1 大值，我們就把這個數(shù)除去幌墓。否則更新前 K + 1 大值但壮。根據(jù)上述描述可以大致估算復雜度。設 K = 233 時克锣，10 ^ {18} 內(nèi)良好的數(shù)的數(shù)量為 N茵肃，經(jīng)過實踐腔长，可以知道 N 約為 50000袭祟。每次擴展最多把一個數(shù)擴展成 \log M 個數(shù)，在剪枝完畢后捞附，列表大小又回歸到 N 以下巾乳，故時間復雜度可以估算為 O(NK Max(p) \log M)，常數(shù)較小鸟召。

B. Harvest of Apples

定義 S(n, m) = \sum_{i = 0} ^ {m} {n \choose i}胆绊，不難發(fā)現(xiàn) S(n, m) = S(n, m - 1) + {n \choose m}, S(n, m) = 2S(n - 1, m) - {n - 1 \choose m}。也就是說欧募，如果我們知道 S(n, m)压状，就能以 O(1) 的代價計算出 S(n - 1, m), S(n, m - 1), S(n + 1, m), S(n, m + 1)，可以采用莫隊算法跟继。

時間復雜度 O(T \sqrt{MAX})种冬。

C. Problems on a Tree

用并查集維護兩種連通塊 —— Easy + Medium 題的連通塊，維護大刑蛱恰娱两；Easy 題的連通塊，維護大小以及與此連通塊只隔一個 Hard 題的 Easy + Medium 連通塊大小之和即可金吗。

D. Nothing is Impossible

如果僅有 1 道題十兢，至少有一個人做對這題需要有 錯誤答案個數(shù) + 1 個人。

那么容易發(fā)現(xiàn)在每道題正確答案只有一個的情況下摇庙，如果 n 道題中存在 s 道題旱物，使得學生人數(shù) m 不少于每道題 錯誤答案個數(shù) + 1 相乘的結(jié)果，那么一定有人能夠得到 s 分卫袒。故我們將題目按錯誤答案個數(shù)從小到大排序异袄，找到最大的 p 滿足 \prod_{i \le p} {(b_i + 1)} \le m 就是答案。

E. Matrix from Arrays

簡單推導可得

M[i][j] = A[(\frac{(i + j)(i + j + 1)}{2} + i) \mod L] = A[(\frac{3i}{2} + \frac{j}{2} + \frac{i ^ 2} {2} + \frac{j ^ 2}{2} + ij) \mod L] = M[i + 2L][j] = M[i][j + 2L]

預處理左上角 2L \times 2L 的矩陣的二維前綴和玛臂，O(1) 回答詢問烤蜕。時間復雜度 O(L ^ 2 + Q)封孙。

F. Travel Through Time

由于可持久化的存在，直接維護哪些位置有棋子十分困難讽营』⒓桑考慮維護一些全是棋子的線段，這些線段可以有重疊部分橱鹏，但是需要保證這些線段覆蓋了所有的棋子膜蠢。

注意到如果我們只維護了線段的左右邊界，甚至不用知道某個左邊界具體對應的是哪個右邊界莉兰，就可以知道某個位置上有沒有棋子挑围。因此只維護左右邊界，把左邊界看成左括號糖荒，右邊界看成右括號杉辙，那么這就是一個括號序列。

比如說對于 0111011110 這樣一串格子（1表示有棋子捶朵，0表示沒有）蜘矢，我們可以用這樣的括號序列來維護：0(111)0(1111)0。由于一個局面并不對應了唯一的括號序列综看，因此這些括號序列也是可以的：0(111)0(11)(11)0品腹，0(1(1(1)))0(((11(11))))0。

對于每一個操作红碑，都可以用括號序列維護：

• 操作一：在 x 前加入一對括號舞吭。

• 操作二：將所有左括號向左移動 x，將所有右括號向右移動 x析珊。

• 操作三：在 l 的前面與 r 的后面加入形如 ... )))((( ... 的括號使得沒有線段穿過 l 和 r羡鸥。然后將 l, r之間的括號直接翻轉(zhuǎn)并反轉(zhuǎn)。比如說對于 0(111)0(11(1)1)0唾琼，如果要翻轉(zhuǎn) [3,8]兄春，首先補充括號，變成：0(1] [11)0(11(1]] [[1)1)0（為了區(qū)分,[與]是新加入的括號）锡溯，然后翻轉(zhuǎn)赶舆，得到：0(1] [[1)11)0(11] [[)1)0。

對于左括號與右括號祭饭，分別開一棵可持久化 Treap 維護即可芜茵。時間復雜度 O(n \log n)。

G. Depth-First Search

由于題目和字典序有關(guān)倡蝙，不妨運用逐位確定的思想九串。

首先，我們要求第一位小于 B_1 的序列總數(shù)，即我們需要快速求出以每個點為根時的DFS序列總數(shù)猪钮。對于有根樹品山，設 f(i) 為以 i 為根的子樹的DFS序列總數(shù)，有

f(u) = |son(u)|! \prod_{v \in son(u)} {f(v)}

我們可以先任選一個根 DFS 求出 f烤低，在第二遍 DFS 考慮祖先的貢獻即可將所有點的答案求出肘交。

接著我們以 B_1 為根，逐位確定求出所有的答案扑馁。和上述方法類似涯呻，即如果當前在 B_i 點，要走到 B_{i+1} 點腻要，需要求出所有第 i + 1 位小于 B_{i+1} 的方案數(shù)复罐，簡單計算即可。

需要注意的是雄家，由于我們可能需要快速計算某個點下某個子樹的名次效诅，所以需要用樹狀數(shù)組或線段樹來優(yōu)化這個過程。

時間復雜度 O(n \log n)咳短。

H. Eat Cards, Have Fun

考慮如何計算某個特定排列 A 的 Value.

Value(A) = \sum_{i = 1} ^ {n} {(n - i)! \sum_{j > i} {[A_j < A_i]}}

這啟發(fā)我們對于每個 i 分別計算貢獻填帽≈肓埽考慮當?shù)?i 張卡片被吃掉的時候咙好，我們需要知道這張卡片左邊、右邊分別已有多少卡片被吃掉（記為 l, r）褐荷，才能確定第 i 張卡片在 A 中的位置勾效；我們還需要知道這張卡片左邊、右邊分別已有多少卡面數(shù)字小于 a_i 的卡片被吃掉（記為 \hat{l}, \hat{r}）叛甫，才能確定第 i 張卡片對答案的貢獻层宫，即 \sum_{j > i} {[A_j < A_i]}。如果知道了 l, r, \hat{l}, \hat{r}其监，那么答案就是

Ans = \sum_{i = 1} ^ {n} \sum_{l = 0} ^ {i - 1} \sum_{r = 0} ^ {n - i} \sum_{\hat{l} = 0} ^ {l} \sum_{\hat{r} = 0} ^ {r} {(n - l - r - 1)! (a_i - 1 - \hat{l} - \hat{r}) P(i, l, r, \hat{l}, \hat{r})}

其中 P(i, l, r, \hat{l}, \hat{r}) 是達到對應情況的概率萌腿。我們可以枚舉第 i 張卡片是在第 k 輪 (k > 0) 被吃掉的來計算概率：

P(i, l, r, \hat{l}, \hat{r}) = {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}} \sum_{k = 1} ^ {\infty} {(1 - (1 - p) ^ k) ^ l ((1 - p) ^ k) ^ {i - 1 - l} p (1 - p) ^ {k - 1} (1 - (1 - p) ^ {k - 1}) ^ r ((1 - p) ^ {k - 1}) ^ {n - i - r}}

其中 b_i = \sum_{j < i} {[a_j < a_i]}.

觀察式子 (1 - (1 - p) ^ x) ^ y，可以用二項式定理展開：

(1 - (1 - p) ^ x) ^ y = \sum_{i = 0} ^ {y} {{y \choose i} (-1) ^ i (1 - p) ^ {xi}}

利用上述結(jié)論抖苦，進一步化簡：

\begin{aligned} & \sum_{k = 1} ^ {\infty} {(1 - (1 - p) ^ k) ^ l ((1 - p) ^ k) ^ {i - 1 - l} p (1 - p) ^ {k - 1} (1 - (1 - p) ^ {k - 1}) ^ r ((1 - p) ^ {k - 1}) ^ {n - i - r}} \\ = & p \sum_{k = 1} ^ {\infty} {(1 - p) ^ {k(i - 1 - l) + k - 1 + (k - 1)(n - i - r)} \sum_{x = 0} ^ {l} {{l \choose x} (-1) ^ x (1 - p) ^ {xk}} \sum_{y = 0} ^ {r} {{r \choose y} (-1) ^ y (1 - p) ^ {y(k - 1)}}} \\ = & p \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \sum_{k = 1} ^ {\infty} {(1 - p) ^ {k(i - 1 - l) + k - 1 + (k - 1)(n - i - r) + xk + y(k - 1)}}} \\ = & p \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \sum_{k = 0} ^ {\infty} {(1 - p) ^ {k (n - l - r + x + y) + (i - 1 - l + x)}}} \\ = & p \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {i - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}} \end{aligned}

至此毁菱，我們獲得了一個時間復雜度為 O(n ^ 5) 的算法。上述公式顯然有不少冗余锌历，可以進一步優(yōu)化贮庞。

回顧原式：

Ans = p \sum_{i = 1} ^ {n} \sum_{l = 0} ^ {i - 1} \sum_{r = 0} ^ {n - i} {(n - l - r - 1)! (\sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {i - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}}) (\sum_{\hat{l} = 0} ^ {l} \sum_{\hat{r} = 0} ^ {r} {(a_i - 1 - \hat{l} - \hat{r}) {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}})}

以下將定義若干輔助函數(shù)加速計算答案。

定義 F：
F(i, l, r) = \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {i - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}}

考慮如何快速計算 F究西。不妨定義 F_n：

F_n(l, r) = \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {n - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}}

顯然 F(i, l, r) = F_n(l, r) (1 - p) ^ {i - n}窗慎。

F_n(l, r) = l! r! \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {\frac{(-1) ^ x} {x!} \frac{(-1) ^ y} {y!} \frac{(1 - p) ^ {n - 1 - (l - x)}} {(l - x)! (r - y)! (1 - (1 - p) ^ {n - (l - x) - (r - y)})}}

令 G(x, y) = \frac{(1 - p) ^ {n - 1 - x}} {x! y! (1 - (1 - p) ^ {n - x - y})}：

F_n(l, r) = l! r! \sum_{x = 0} ^ {l} {\frac{(-1) ^ x} {x!} \sum_{y = 0} ^ {r} {\frac{(-1) ^ y} {y!} G(l - x, r - y)}}

可以在 O(n ^ 3) 的時間計算出 F_n。

定義 L, R, L_{+}, R_{+}, H：

L(i, l) = \sum_{\hat{l} = 0} ^ {l} {{b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}}}, R(i, r) = \sum_{\hat{r} = 0} ^ {r} {{a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}}

L_{+}(i, l) = \sum_{\hat{l} = 0} ^ {l} {\hat{l} {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}}}, R_{+}(i, r) = \sum_{\hat{r} = 0} ^ {r} {\hat{r} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}}

H(i, l, r) = \sum_{\hat{l} = 0} ^ {l} \sum_{\hat{r} = 0} ^ {r} {(a_i - 1 - \hat{l} - \hat{r}) {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}} = (a_i - 1) L(i, l) R(i, r) - L_{+}(i, l) R(i, r) - L(i, l) R_{+}(i, r)

以 O(n ^ 3) 的代價預處理 L, R, L_{+}, R_{+}, 可以在 O(n ^ 3) 的時間計算出 H。

現(xiàn)在 Ans 就可以在 O(n ^ 3) 的時間計算出來啦遮斥。

Ans = p \sum_{i = 1} ^ {n} \sum_{l = 0} ^ {i - 1} \sum_{r = 0} ^ {n - i} {(n - l - r - 1)! F_n(l, r) (1 - p) ^ {i - n} H(i, l, r)}

I. Delighful Formulas

根據(jù)題意列出式子：

Ans = \sum_{i = 1} ^ {N} {[\gcd(i, N) = 1] \sum_{j = 1} ^ {i} {j ^ K}}

莫比烏斯反演：

\begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {N} {[d \mid i] \sum_{j = 1} ^ {i} {j ^ K}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} 1zrp11d} \sum_{j = 1} ^ {id} {j ^ K}}\end{aligned}

定義 F：

F_p(N) = \sum_{i = 1} ^ {N} {i ^ p}

顯然 F_p 是 p + 1 階多項式：

F_p(N) = \sum_{i = 0} ^ {p + 1} {a_{p, i} N ^ i}

利用 F 化簡原式：

\begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} djj3fvf} {F_K(id)}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} vxndxht} \sum_{j = 0} ^ {K + 1} {a_{K, j} (id) ^ j}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j \sum_{i = 1} ^ {\frac{N} pvh3phz} {i ^ j}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j F_j(\frac{N}hz3d31d)}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j \sum_{k = 0} ^ {j + 1} {a_{j, k} (\frac{N} 1dtnlnj) ^ k}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = -1} ^ {K + 1} {d ^ i \sum_{j = 0} ^ {K + 1} \sum_{k = 0} ^ {j + 1} {[j - k = i] a_{K, j} a_{j, k} N ^ k}}} \end{aligned}

定義 G：

G_i = \sum_{j = 0} ^ {K + 1} \sum_{k = 0} ^ {j + 1} {[j - k = i] a_{K, j} a_{j, k} N ^ k}

利用 G 化簡原式：

\begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = -1} ^ {K + 1} {d ^ i G_i}} \\ & = \sum_{i = -1} ^ {K + 1} {G_i \sum_{d \mid N} {\mu(d) d ^ i}} \\ & = \sum_{i = -1} ^ {K + 1} {G_i \prod_{p \mid N} {(1 - p ^ i)}} \end{aligned}

如果我們能快速計算出 G峦失，就可以在 O(MK) 的時間計算答案，其中 M 為質(zhì)因子個數(shù)术吗。

將 G 用伯努利數(shù)展開宠进，可以發(fā)現(xiàn)是卷積的形式，直接 NTT藐翎，時間復雜度 O(K \log K)材蹬。

J. Let Sudoku Rotate

搜索加可行性剪枝即可通過。由于數(shù)獨限制較強吝镣，剪枝效果良好堤器。

K. Expression in Memories

注意在類似 +0? 的情況下，? 須被替換為 + 或 *末贾，其余情況直接將 ? 替換為非零數(shù)字就好闸溃。替換完成后判斷一下是否合法。

L. Graph Theory Homework

容易證明 \lfloor \sqrt{a} \rfloor + \lfloor \sqrt拱撵 \rfloor \ge \lfloor \sqrt{a + b} \rfloor辉川，進而可以證明邊權(quán)滿足三角不等式，故直接從 1 走到 n 就是最優(yōu)的拴测。