題目傳送門

題目背景

有一個奇奇怪怪的火車站，奇奇怪怪的站長JTZ想要解決一個奇奇怪怪的問題。

題目描述

現在有 $N$ 列火車要進出站，對於同一列車進站和出站有且只有一次鳴笛，笛聲有 $1-M$ 種音調，要求相鄰的兩次鳴笛之間音調的差的絕對值不能小於 $K$ （不鳴笛笛聲音調看作$1e100$ ）。不然耳朵不好的車站管理員XYH分不清楚是哪一列車，現在XYH給出了每一列火車的進出，JTZ想知道總共有多少種鳴笛的方案，而他又不想太麻煩，所以只需要方案數除以 $43621789$ 的餘數。
某中學八年級大佬RSJ知道了這個訊息後，覺得太簡單了，幾下算出了結果 $x$ （取餘數後）。於是他想讓你算出 $M^x\mathrm{m}\mathrm{o}\mathrm{d}43621789$ 。

輸入格式

第一行三個整數 $N,M,K$ 。
第二行有 $2N$ 個整數，每個整數是 $0$ 或 $1$ 代表車進站和出站，保證資料合法，也就是說當車站沒有車的時候沒有車出站，最後車站沒有車。

輸出格式

一行，表示答案。( $M^x\mathrm{m}\mathrm{o}\mathrm{d}43621789$ )

輸入輸出樣例

輸入#1

2 1 0
0 0 1 1

輸出#1

1

輸入#2

3 5 2
0 0 0 1 1 1

輸出#2

40308287

提示/說明

圖非常重要

樣例解釋：

樣例1： $x=4,M=1$ 答案為 $1^4\mathrm{m}\mathrm{o}\mathrm{d}43621789=1$
樣例2： $x=250,M=5$ 答案為 $5^{250}\mathrm{m}\mathrm{o}\mathrm{d}43621789=40308287$

資料範圍

本題採用 Subtask
$\text{Subtask}1$: 測試點 $1-5$ $30\%$ $N\le 3,M\le 7$
$\text{Subtask}2$: 測試點 $6-12$ $40\%$ $N\le 100，M\le 7$
$\text{Subtask}3$: 測試點 $13-20$ $40\%$ $N\le 500,M\le 7$
你只有通過每個 $\text{Subtask}$ 的所有測試點才能獲得該 $\text{Subtask}$ 的分值。

---

題目解析

這道題目的出題靈感來自於CF149D。我們只要把火車進站看成左括號，火車出站看成右括號。其實應該是棧。
排列與組合是行不通的，因為對於同一列車進站和出站有且只有一次鳴笛，由於沒有要求輸出步驟，又可以搜尋，考慮DP。無疑是區間DP，因為對於鳴笛的音調會影響到其他的方案數量，那麼需要將左右側的鳴笛音調列入方程轉移式。
令函數 $f(i,j,x,y)$ 為區間 $[i,j]$ 中，左右端點中，左端點的鳴笛音調為 $x$ ，右端點的鳴笛音調為 $y$ 的種數。不鳴笛記為 $0$ 。分兩種情況考慮。
我們需要預處理出輛火車的進出站，存在陣列裡，要求能 $\Theta (1)$ 查詢。
情況一：第 $i$ $j$ 次進出站時相同的車。
那麼我們需要列舉 $i,j$ 的音調以及相鄰的 $i+1,j-1$ 的音調，並且要保證資料合法。
$$f(i,j,x,y)=\sum f(i+1,j-1,a,b)$$
其中 $|a-x|\ge k$ 或者 $x=0,a\ne 0$ 或者 $x\ne 0,a=0$
並且 $|b-y|\ge k$ 或者 $b=0,y\ne 0$ 或者 $b\ne 0,y=0$
並且 $x=0,y\ne 0$ 或者 $x\ne 0,y\ne 0$

情況二：第 $i$ $j$ 次進出站時不是相同的車。
設第 $i$ 輛車的出站為 $mid$ ，那麼就可以將區間 $[i,j]$ 分割成區間 $[i,mid],[mid+1,j]$ ，然後列舉四個端點音調的即可，也要保證資料合法。
$$f(i,j,x,y)=\sum f(i,mid,x,a)\times f(mid+1,b,y)$$
其中 $|a-b|\ge x$ 或者 $a=0,b\ne 0$ 或者 $a\ne 0,b=0$
並且 $x=0,a\ne 0$ 且 $x\ne 0,a=0$ （因為 $x,a$ 同一輛車）

最後注意一些細節就可以了。
演演算法複雜度是 $\Theta \left(N^2{M}^4+N\right)$ 的，雖然可以優化成 $\Theta \left(N^2{M}^3+N\right)$ 但是因為我懶所以我就不寫了。

最後記得輸出 $M^x\mathrm{m}\mathrm{o}\mathrm{d}43621789$ ，記得加上快速冪和 long long。