..
Distance to Different: A Enumeration Problem
昨天下午坐高鐵從上海回西安，何給我推薦了一道有趣的計數題。看了下，發現我其實和何一起打了遮場 EDU，但我卻完全沒有補題，真是慚愧。
首先思考有哪些序列会是合法的 $b$，發現 $b$ 必然要满足下列的性質：
- $1$ 不能單獨出現；
- 若有 $t, t>1$ 出現，那麼一定存在 $x\geq t$，使得 $t$ 存在於 $[1,2,\ldots,x,x,\ldots,2,1]$ 或 $[1,2,\ldots,x,\ldots,2,1]$ 中。
我們發現可以将原序列理解成一個個長度不同的塊，並且相鄰塊之間的數的具體值並不影響 $b$，也就是說我們可以僅用 $0,1$ 兩個數字構造出 $b$。換言之，對於滿足以上兩條性質的 $b$，總能够構造出來，所以祇要思考滿足性質的 $b$ 有幾種。可以發現，如果塊長大於 $2$，解釋祇能是連續的段；若塊長為 $2$，則對應在 $b$ 中的子串為 $[1,1]$，遮可以有兩種解釋：
- 兩個相同的數；
- 兩個不同的數。
注意到題目還有一個限制，至少有 $k$ 種數字，也就是至少有 $k$ 個塊。於是我們可以把 $[1,1]$ 祇理解為兩個不同的數。為了計數，考慮狀態 $f(i,k)$ 表示當前總長為 $i$，至少有 $k$ 個塊，且沒有塊長為 $2$ 的情況數。答案為
\[f(n,k)+2f(n-2,k-1)+f(n-4,k-2),\]且有如下轉移方程：
\[f(i,k)=\sum_{j=1}^{i}f(i-j,k-1) - f(i-2,k-1).\]利用前綴和優化動態規劃，時間複雜度為 $O(nk)$。
仔細觀察可以發現，每次迭代 $k$ 時的轉移都是相同的，其實是卷積。記 $f(i,k)$ 為多項式 $P^{(k)}(x)$ 中 $x^{i}$ 的系數，則有：
\[P^{(k+1)}(x)=P^{(k)}(x)\times (x^1+x^3+x^4+\ldots).\]我們記
\[T(x)=x^1+x^3+x^4+\ldots,\]則有：
\[P^{(k)}(x)=P^{(0)}(x)\times T^{k}(x),\]其中，$P^{(0)}(x)$ 是初始的情況，也就是沒有 $k$ 的限制時的答案。滿足：
\[\begin{cases} f(i,0)=0,&i<0;\\ f(i,0)=1,&i=0;\\ f(i,0)=\sum_{j=0}^{i-1}f(j,0)-f(i-2,0),&\text{otherwise}. \end{cases}\]遮是個線性遞推式，可以在 $O(n)$ 時間中計算出 $P^{(0)}(x)$ 的前 $(n+1)$ 項。所以答案可以通過快速傳立葉變換得出，時間複雜度為 $O(n\log n \log k)$。
由於
\[\begin{align} T(x)&=x+x^3+x^4+\ldots\\ &=\frac{x}{1-x}-x^2\\ &=x\frac{1-x+x^2}{1-x}\\ &=x\frac{1+x^3}{1-x^2}. \end{align}\]或許有技巧能更快地計算答案。