Solution -「多校聯訓」I Love Random

\(\mathcal{Description}\)

  給定排列 \(\{p_n\}\)，可以在其上進行若幹次操作，每次選取 \([l,r]\)，把其中所有元素變為原區間最小值，求能夠得到的所有不同序列數量。答案對 \((10^9+7)\) 取模。

  \(n\le5\times10^3\)。

\(\mathcal{Solution}\)

  一類題型一起寫啦，再給出一道類似的題：

  給定字元串 \(s\)，\(s_i\in\{\text{'R'},\text{'G'},\text{'Y'}\}\)，每次允許交換相鄰兩個元素。求最少交換次數，使得 \(s\) 中不存在兩個相鄰元素相等，或聲明無解。   \(n\le400\)。

  不難看出它們都是 DP 題，但是若以從左到右的視角考慮問題，給定的操作具有強後效性，很難設計出一種靠譜的狀态。

  這個時候可以奉行“拿來主義”（？），直接構造結果序列，将問題轉化為把原序列上某值拿到結果序列的某位置的最小操作次數 / 方案數，再根據實際情況設計算法就很友善了。

  例如，對于求方案數的這題，令 \(f(i,j)\) 表示構造了結果序列的前 \(i\) 位，第 \(i\) 位用的是原序列的 \(p_j\) 的方案數。根據較大值不能覆寫較小值設計轉移即可；對于最小化操作次數這題，令 \(f(i,r,g,k\in\{0,1,2\})\) 表示構造了結果序列前 \(i\) 位，用了 \(r\) 個 <code>R</code>，\(g\) 個 <code>G</code>，（\((i-r-g)\) 個 <code>Y</code>，）最後一個位置顔色為 \(k\) 的最小代價。轉移利用類似冒泡排序的性質，在原序列裡拿一個最近的顔色的目前位置即可。

  隻給那道計數題的代碼叭。