由于都是 CF 上非賽時做的題，是以所有代碼都可以去 CF 上找我的賬号 zimujun 的 submission 檢視。
每道題的标題上有題目連結。
目錄
- 1559E Mocha and stars
- 1550E Stringforces
- 1246C Rock is Push
*2200，考察基本數論函數性質、背包 dp 和字首和優化的綜合應用，屬于綜合性較強的基礎題。
求有多少長度為 \(n\) 的序列 \(\{a_i\}\) 滿足 \(\forall i \in [1, n]\cap\mathbb Z, l_i \le a_i \le r_i, \displaystyle\sum_{i = 1} ^ n a_i \le m, \gcd(a_1, a_2, \cdots, a_n) = 1\)。
\(n \le 50, l_i \le r_i \le m \le 10 ^ 5\)。
\[\displaystyle ans = \sum_{i_1 = l_1} ^ {r _1}\sum_{i_2 = l_2} ^ {r_2} \cdots\sum_{i_n = l_n} ^ {r_n}\left[\sum_{j = 1} ^ n i_j \le m\right]\left[\gcd(i_1, i_2, \cdots, i_n) = 1\right]\\
=\sum_{i_1 = l_1} ^ {r _1}\sum_{i_2 = l_2} ^ {r_2} \cdots\sum_{i_n = l_n} ^ {r_n}\left[\sum_{j = 1} ^ n i_j \le m\right]\sum_{t \mid \gcd(i_1, i_2, \cdots, i_n)}\mu\left(t\right)\\
=\sum_{t = 1} ^ m\mu\left(t\right) \left(\sum_{i_1 = \lceil \frac{l_1}{t}\rceil} ^ {\lfloor \frac{r_1}{t}\rfloor}\sum_{i_2 = \lceil \frac{l_2}{t}\rceil} ^ {\lfloor \frac{r_2}{t}\rfloor}\cdots\sum_{i_n = \lceil \frac{l_n}{t}\rceil} ^ {\lfloor \frac{r_n}{t}\rfloor}\left[\sum_{j = 1} ^ n i_j \le \lfloor\frac{m}{t}\rfloor\right]\right)\]
後面那個 dp 求解就好，由于上界隻到 \(\lfloor\dfrac{m}{t}\rfloor\) 是以總的複雜度是 \(O(nm\ln m)\) 的。
具體的，設 \(f(i, j)\) 表示在前 \(i\) 個數中選出的總和為 \(j\) 的方案數，顯然有 \(\displaystyle f(0, 0) = 1, f(i, j) = \sum_{k = \lceil\frac{l_i}{t}\rceil} ^ {\lfloor\frac{r_i}{t}\rfloor} f(i - 1, j - k)\)，不難發現後面這個轉移可以一個字首和搞掉，最後答案即為 \(\displaystyle \sum_{i \le \lfloor\frac{m}{t} \rfloor} f(n, i)\)。
*2500，考察二分和狀壓，同時涉及部分貪心政策的應用，解法較為巧妙。
要求使得最小值最大，可以考慮二分一個限制指 \(len\)，要求這 \(k\) 種字元連續出現的最大次數都大于 \(len\)，然後判斷這個限制值是否合法。
可以考慮然把這 \(k\) 個長度為 \(len\) 的連續段放入字元串的一個字首，因為當沒有别的限制的時候，我們肯定會選擇貪心地加入，使得已經加入的字首盡可能短，可以證明這樣的構造方案一定不會更劣。
但是現在有确定字元的限制，而且不同種類字母的限制不同（被除了目前種類字字母在内的所有其他字母限制）。看到 \(k \le 17\)，考慮狀壓。
設 \(f(S)\) 表示已經加入的字母種類集合為 \(S\) 時所占字首的最小長度。通過枚舉往集合中新加入的字元刷表轉移。最後判斷 \(len\) 是否合法即可轉化為判斷 \(f(\{1,2,\cdots,k\}) \le n\) 是否成立，考慮如何優雅地實作這個轉移。
做一個預處理，設 \(next(i,j)\) 表示從第 \(i\) 個位置，放長度為 \(len\) 的第 \(j\) 種字母的連續段，可以放到的最小右端點位置。倒序枚舉 \(i\)，如果後面 \(len\) 長度内出現了除了
?
和第 \(j\) 種字母之内的其他字元（通過維護已經掃過去的每一種字元最靠左的位置實作即可），那就把 \(next(i, j)\) 指派為 \(next(i + 1, j)\)，如果沒有出現，那就是 \(i + len\)。這樣處理一遍的複雜度為 \(O(nk)\)。
完成這個預處理，我們就可以實作這個轉移了。
\[\large f(S) = \min_{T\subsetneqq S\land T\cup\{i\} = S}\left\{next(f(T), i)\right\}
\]
枚舉狀态和字元轉移即可，複雜度為 \(O(k2^k)\)。
總的複雜度為 \(O((nk + k2^k)\log n)\)。
*2200，考察對題目性質的發現和使用 dp 求解問題的能力。
前幾天 vp 的時候沒做出來的一道題。
看起來很 npc 的題意，沒想到是個 dp，後來一想，如果把方案數按下一步向左還是向下走區分開，那麼這樣确實滿足無後效性。
然後一個字首和優化就做完了。
很有意思的一道題。
（要是具體做法還不太明白的話私戳我吧）