怎么又是大模擬 xd

2024暑期CSP-S&NOIP模擬賽第4套

鏈接：link
題解：link

時間：4.5h (2025.10.26 07:30~12:00)
題目數：4
難度：

估分：100 + 83 + 100 + 8 = 291
得分：90 + 47 + 100 + 0 = 237
Rank：2/6

場祭

讀題。

A 簽。

B 怎么是大模擬，推了推發現重點是 \(p \oplus q\) 的奇偶性，但是情況非常多，特判一大坨 /tuu

看了眼 C，直接放線段樹板子？

還是先寫 B，寫寫寫，怎么過樣例了？不是這大樣例怎么這么弱？還只給一個？甚至沒有任何 max 操作甚至沒有無解情況？出題人是認為這是在打 ACM 嗎？

不管了，先寫 C 去了。

然后開 D，發現不怎么會。

回來查 B，哦輕而易舉地 hack 掉了自己，然后寫寫寫調調調發現處理不了把非 \(p_i \ne 1\) 插入到 \(p_j = 1\) 的中間的情況，就是說前面那個情況 \(t_j < t_i\)，因為 max 標記是沒法刪除的?？紤]把 \(p_i = 1\) 都放到一塊，從前往后存每個 max 標記，但是又發現在 \(p_i = 1\) 中間插入 \(p_i = 1\) 的復雜度還是不對的，于是不管了拍個暴力上去走人了。

……實際上是因為沒時間了。

30min 先把 D 特殊性質寫掉，然后發現會了 \(O(n^3 \log n)\) 的做法，寫寫寫，沒過樣例！

補題

B 掛了一坨感覺很正常的。

A 是掛 corner case 了。

補 D，我嘞個頂級 dp 優化（

先是一步容斥，轉化為求不包含 \(i\) 的方案數

考慮一個暴力地不能再暴力的 dp，令 \(f_{i,w}\) 為前 \(i\) 個，\(i\) 必選，選擇的以 \(i\) 結尾的區間的 gcd 為 \(w\) 的方案數，則枚舉這一個選擇的區間的開始位置、上一個選擇的區間結束位置，有轉移：

然后注意到 \(w\) 只有 log 種取值，而 \(\gcd \{ a_j \ldots a_i \} = w\) 中當 \(w\) 固定的時候，\(j\) 的取值范圍是容易維護的。

關于 \(j\) 的范圍如何維護：考慮如果已經知道了 \(i-1\) 對應的所有區間（用一個四元組表示為 \((l,r,w,i-1)\)，含義顯然），那么在推到 \(i\) 的時候，先把 \((i,i,a_i,i)\) 加入，然后依次往前判個 gcd 后合并就可以了。

所以 \(j\) 的枚舉就可以從 \(O(n)\) 變成 \(O(\log V)\) 的了。

但是 \(k\) 的枚舉省不了??！因為 \(w\) 總共有 \(O(n \log V)\) 種取值，沒法直接前綴和。

然后復雜度就卡在了 \(O(n^2 \log V)\) 上了，而且是難優化的。

然后就是想不到的了，考慮直接維護 \(g_{i,w}\) 表示 \(1 \sim i\) 種選若干個 gcd 為 \(w\) 的區間的方案數。然后發現這個東西還是很好轉移的：

• 如果不選 \(i\)，則 \(g\) 值不會產生任何變化，即：

  \[g_{i,w} \gets g_{i-1,w} \]

• 如果選，那必須存在一個四元組 \((l,r,w,i)\)，則可以選一個區間 \([j,i]\) 轉移，有：

  \[g_{i,w} \gets g_{i-1,w} + \sum _{j=l} ^r (g_{j-1,w} + 1) \]

  其中 \(+1\) 是因為可以只選 \([j,i]\) 這一個區間。

然后發現這玩意能上線段樹就做完了（

B 做法大體是對的，但是細節太多了，懶得補。祈禱正式賽不會再出大模擬了吧 XD，反正 NOIP 不出就行，CSP-S 倒是無所謂。

天依寶寶可愛！