AGC 的題都比較有情趣。

Description

對于一個長為 \(3n\) 的排列 \(a\)，使用其生成等長的排列 \(p\)，生成方法如下：

• \(p\) 初始為空。
• 將序列 \(a\) 等分成 \(n\) 段，第 \(k(0\le k<n)\) 段包含 \(a_{3k+1},a_{3k+2},a_{3k+3}\)。
• 定義 \(n\) 個指針，初始分別指向每段中的第 \(1\) 個元素，即 \(a_{3k+1}\)。
• 執行若干次下面的操作，直到所有指針均被銷毀：尋找當前所有指針指向元素的最小的一個，將該元素放在 \(p\) 的最后面，并讓指向該元素的指針右移 \(1\)，若移出當前所在段，則銷毀該指針。

求總共能生成出多少不同的 \(p\) 序列，對 \(m\) 取模。

\(1\le n\le 2000,10^8 \le m \le 10^9+7\)

Analysis

一個顯然的思路方向是關心 \(p\) 能否被生成出來。不難發現，如果存在 \(i<j \land p_i > p_j\)，那么 \(p_i,p_j\) 必定被分在原序列 \(a\) 的同一段中。

接下來又發現 \(p_i,p_j\) 必定還滿足相鄰或只隔了一個數（而且隔開的這個數也與他們在同一段內），這是一個必要條件。這個必要條件看上去非常迂蠢，因此找到 \(p\) 的前綴 \(\max\) 數組 \(h\)，發現這個條件等價于 \(h\) 中連續段長度不超過 \(3\)。

于是可以先將 \(p\) 的前綴 \(\max\) 數組日出來，分出 \(k\) 個段。

例如 \([3,1,2,4,6,5]\to[3,3,3,\mid 4 \mid 6, 6]\)，構造 \(a=\lang 3, 1,2,4,6,5\rang\) 即可。

然后列著列著 \([3,1,4,2,6,5] \to [3,3 \mid 4,4 \mid 6,6]\)，然后嘗試構造，有這幾條限制，\(3\) 與 \(1\)、\(4\) 與 \(2\)、\(6\) 與 \(5\) 在同一個三元組中，然后仔細一瞧，喲，似了。由于三元組只有兩個，所以每個二元段都必須要搞出第三個數，然而在該序列中全為 \(2\) 元段，所以搞不出單獨的第三個數。

所以自然而然地想出 \(p\) 的前綴 \(\max\) 數組 \(k\) 個段中，長度為 \(2\) 的數量必須少于長度為 \(1\) 的數量，不然湊不出來了。

那么尋求普遍性，是不是所有滿足這個條件的 \(p\) 一定存在一個 \(a\) 與之對應？

假設 \(s_i=\max\limits_{j\le i}\{p_j\}\) 有 \(k_1\) 個長為 \(1\) 的連續段，\(k_2\) 個長為 \(2\) 的連續段。滿足 \(k_1 \ge k_2\)。

長為 \(3\) 的連續段對構造無影響（直接給它們放一塊就可以聽候安排了），可以不妨設不存在。

先嘗試著消掉所有 \(2\) 連續段：假如存在一個 \(1\) 連續段排在他前/后，那么就組建一個 \(a\) 中的三元段，讓該 \(2\) 連續段的前/后放上這個孤獨的數。

剩下的 \(1\) 連續段直接按順序排即可。

這樣構造的合理性在于，由于是前綴最大值，單調遞增，這樣構造后一定會先將前綴最大值所在組按順序干掉，只需考慮單個三元段中的順序即可。

Solution

于是可以使用 \(\rm dp\)，令 \(f_{i,j}(i\in[1,3n],j\in[-n,n])\) 為考慮到第 \(i\) 位，限制當前第 \(i\) 位為最后一個前綴 \(\max\) 連續段的末尾，\(1\) 段個數減 \(2\) 段個數為 \(j\) 的方案數。

轉移

\(\mathrm{ans}=\displaystyle\sum_{j\ge0} f_{3n,j}\)。

如果多加仔細觀察的話，會發現此處的轉移之所以如此之簡單，還有一個重要的 \(\rm dp\) 思想，就是由于前面得到的 \(\rm dp\) 值是只考慮到第 \(x\) 位，填的是 \(1 \sim x\) 的數，轉移到當前的第 \(i\) 位，顯然這里也只填從 \(1 \sim i\)，當前塊第一個放的一定是 \(i\)，第二個和第三個先欽定為 \(i-1,i-2\)，再在前面找到數與之交換（也可不交換）由于 \(i-1,i-2\) 均是大于前面的數的，所以對合法性無影響。