I - Cow Families

有若干個 $1$ 到 $m$ 的數字，數字 $i$ 恰好有 $a_i$ 個。請問有幾種排列，使得它的最長嚴格遞增子序列(LIS) 長度恰好是 $m$？條件限制 $1\le m\le 50$，所有 $i$ 滿足 $1\le a_i\le 50$。

題解

有一個很重要的觀察，由於所有數字只有 $1$ 到 $m$ 的整數，因此 LIS 長度為 $m$ 的時候這條 LIS 必定是 $1, 2, 3, \cdots, m$。

接下來有個觀察，徹底刻畫我們要的性質：

性質

若我們由左而右，將依序出現的第一個 $1, 2, \cdots, m$ 標記起來（例如 $3, 1, 3, 2, 1, 3$，我們會標記第 $2, 4, 6$ 個數字）我們會發現：有標記的數字 $i$ 和有標記的數字 $i-1$ 之間，一定不會出現任何數字 $i$（廢話）

但是這個廢話卻是至關重要的...廢話！

假想一下，我們依照以下方法建造所有 LIS 恰好是 $m$ 的序列：讓 $i$ 從 $1$ 跑到 $m$，每一次一口氣把全部的 $a_i$ 個 $i$ 一起塞進 sequence 裡面。

動態規劃

怎麼塞呢？如此一來我們的狀態就很清楚了：「現在做到數字 $i$」、「被標記的數字 $i$ 出現在第 $k$ 個位子上」。第一個維度是 $O(n)$，第二個維度是 $O(\Sigma a_i) = O(n^2)$。

接下來是轉移，我們可以考慮的是，被標記的那個 $i$ 是所有 $a_i$ 個 $i$ 之中的第 $j$ 個！然後枚舉一下被標記的 $i-1$ 出現的位置 $\ell$。於是利用一點點的組合數我們可以寫下：

$dp[i][k] = \displaystyle\sum_{j=1}^{a_i} \displaystyle\sum_{1\le \ell\lt k} dp[i-1][\ell] {\binom{\ell-1+j-1}{j-1}}{\binom{(a_1+\cdots+a_i) - k}{a_i-j}}$

當然如果直接照著這個遞迴關係實作，就會得到一個 $O(n^6)$ 的作法，TLE。

多看兩眼

我們觀察遞迴關係的第三項，發現這一項與 $\ell$ 並無任何關係！因此我們可以把這一項搬到前面去：

$dp[i][k] = \displaystyle\sum_{j=1}^{a_i} {\binom{(a_1+\cdots+a_i) - k}{a_i-j}} \displaystyle\sum_{1\le \ell\lt k} dp[i-1][\ell] {\binom{\ell-1+j-1}{j-1}}$

令 $c_{j,k} = \sum_{1\le \ell\lt k} dp[i-1][\ell] {\binom{\ell-1+j-1}{j-1}}$，我們有：

$c_{j,k+1} = c_{j,k} + dp[i-1][k]{\binom{k-1+j-1}{j-1}}$

於是原式就會變成

$dp[i][k] = \displaystyle\sum_{j=1}^{a_i} {\binom{(a_1+\cdots+a_i) - k}{a_i-j}} c_{j,k}$

就得到一個 $O(n^4)$ 的解了！

評論

這題稍微可惜了些...相較於後面的 Problem J, K, L，這題應該是最有機會在賽中被做出來的！

故事

這題是去年我出給 UMich 作為練習的唯二題目之一，當初做這題的時候自信滿滿跟 Mark (若干年前拿過 ICPC 第二名的強者) 說我可以做到 $n=200$，然後馬克做了很久跟我說...「只能做到 $n^4$ 耶...」然後我就做不出來了XD