樸素析合樹(shù)計(jì)數(shù)相關(guān)

從前從前有只貓頭鷹
它站在屋頂
屋頂后面一片森林
森林很安靜
安靜的鋼琴在大廳
閣樓里 仔細(xì)聽(tīng)
仔細(xì)聽(tīng) 叮叮叮
什么聲音
乖乖睡 不要怕 聽(tīng)我說(shuō)
乖乖睡 醒來(lái)就 吃蘋(píng)果
不睡覺(jué) 的時(shí)候 有傳說(shuō)
會(huì)有人 咬你的 小指頭
這故事 繼續(xù)翻頁(yè) 再翻頁(yè)
你繼續(xù) 不想睡 我卻想睡
然后我準(zhǔn)備去打開(kāi)衣柜
去看看 躲著誰(shuí)
去看看 躲著誰(shuí)
紙上的城堡卡片
發(fā)光的立體呈現(xiàn)
奇幻的床邊故事
動(dòng)聽(tīng)的令人稱(chēng)羨
場(chǎng)景瞬間變化
我接著又施展魔法
活過(guò)來(lái)說(shuō)話(huà)
準(zhǔn)備開(kāi)始吧
等天黑一起倒數(shù)后關(guān)上燈
三二一 入夢(mèng)境的繽紛
我們并非正常人
游戲怎么會(huì)照劇本 oh
天黑一起來(lái)關(guān)上燈
三二一 進(jìn)自由的靈魂
Ohohohoh oh come on
再回童年 敲敲門(mén)
滴噠滴噠突然開(kāi)始擺動(dòng)
墻上老掛鐘
古董油畫(huà)出現(xiàn)詭異的笑容
好的巫婆壞掉的蘋(píng)果
愿望要跟誰(shuí)說(shuō)
旋轉(zhuǎn)的音樂(lè)盒
我豎起耳朵聽(tīng)
這不會(huì)是一場(chǎng)夢(mèng)
Oh 夢(mèng) 一下子瞬間跳躍
我翻閱下個(gè)世界
滿(mǎn)滿(mǎn)都是蝴蝶
森林滿(mǎn)滿(mǎn)蝴蝶
窗外紛飛著雪
一覺(jué)醒來(lái)旁邊躺著是誰(shuí)
這故事 繼續(xù)翻頁(yè) 再翻頁(yè)
你繼續(xù) 不想睡 我卻想睡
然后我準(zhǔn)備去打開(kāi)衣柜
去看看 躲著誰(shuí)
去看看 躲著誰(shuí)
紙上的城堡卡片
發(fā)光的立體呈現(xiàn)
奇幻的床邊故事
動(dòng)聽(tīng)的令人稱(chēng)羨
場(chǎng)景瞬間變化
我接著又施展魔法
活過(guò)來(lái)說(shuō)話(huà)
準(zhǔn)備開(kāi)始吧
等天黑一起倒數(shù)后關(guān)上燈
三二一 入夢(mèng)境的繽紛
我們并非正常人
游戲怎么會(huì)照劇本 oh
天黑一起來(lái)關(guān)上燈
三二一 進(jìn)自由的靈魂
Ohohohoh oh come on
再回童年 敲敲門(mén)
乖乖睡啊 不要害怕
乖乖睡醒來(lái)就吃蘋(píng)果啊
不睡覺(jué)啊 有傳說(shuō)啊
會(huì)有人咬你的小指頭啊
等天黑一起倒數(shù)后關(guān)上燈
三二一 入夢(mèng)境的繽紛
我們并非正常人
游戲怎么會(huì)照劇本 oh
天黑一起來(lái)關(guān)上燈
三二一 進(jìn)自由的靈魂
Ohohohoh oh come on
再回童年 敲敲門(mén)
再回童年 敲敲門(mén)
再回童年 敲敲門(mén)

這里只講析合樹(shù)的計(jì)數(shù)相關(guān)部分，即計(jì)數(shù)析合樹(shù)個(gè)數(shù)，甚至不講如何建析合樹(shù)。沒(méi)準(zhǔn)以后會(huì)寫(xiě)

樸素析合樹(shù)是對(duì)于特化析合樹(shù)叫的，就是一般的析合樹(shù)。

設(shè)排列是 \(P\)。

定義連續(xù)段是 \([l, r] \text{ s.t.} \max_{i\in [l, r]} P_i - \min_{i\in [l, r]} P_i = r - l\)。

容易發(fā)現(xiàn)連續(xù)段不可能?chē)?yán)格相交（即不算包含），且一個(gè)點(diǎn)一定是連續(xù)段。

我們建出這個(gè)樹(shù)形結(jié)構(gòu)，叫做析合樹(shù)。

定義合點(diǎn)是一個(gè)點(diǎn)滿(mǎn)足其任意一個(gè)非平凡連續(xù)兒子（即長(zhǎng)度不為 \(1\) 且不是全部）都是連續(xù)段。

定義析點(diǎn)是不是合點(diǎn)的點(diǎn)。

葉子節(jié)點(diǎn)和只有兩個(gè)兒子的點(diǎn)其實(shí)定義成析點(diǎn)還是合點(diǎn)都無(wú)所謂，這里我們采用廣泛的定義定義其是合點(diǎn)。

定義一個(gè)點(diǎn)的兒子排列是取出其所有兒子所表示的區(qū)間的左端點(diǎn)并離散化形成的排列，也叫其兒子序列，容易發(fā)現(xiàn)合點(diǎn)的排列是升序或降序的。

析點(diǎn)滿(mǎn)足其任意一個(gè)非平凡連續(xù)兒子（即長(zhǎng)度不為 \(1\) 且不是全部）都不是連續(xù)段。

這個(gè)性質(zhì)挺讓人迷惑的，但是證明其實(shí)不難，考慮到其若有非平凡連續(xù)兒子形成連續(xù)段則可以將這些兒子縮成一個(gè)合點(diǎn)。

考慮一些計(jì)數(shù)相關(guān)的事情。

考慮求一個(gè)長(zhǎng)為 \(l\) 合點(diǎn)的方案數(shù)，其實(shí)非常的簡(jiǎn)單，考慮枚舉其第一個(gè)兒子的長(zhǎng)度 \(k\)，于是我們要找一個(gè)長(zhǎng)為 \(k\) 的排列且其任意前綴都不是連續(xù)段，設(shè)其數(shù)量是 \(g_k\)，顯然有單步容斥遞推式：

可以 \(n\log n\) 甚至 \(\frac {n\log^2 n}{\log\log n}\) 甚至 \(n \log^2 n\) 甚至 \(n ^ 2\) 求出。

所以最后答案是 \(2\sum_{i = 1}^{n - 1}g_i(n - i)!\)，注意可以正或反要乘 \(2\)。

考慮求一個(gè)長(zhǎng)為 \(l\) 的析點(diǎn)方案數(shù)，我們有一個(gè)取巧的辦法，就是用所有排列數(shù)減掉合點(diǎn)方案數(shù)。當(dāng)然這并不能很好的解決有一些限制的問(wèn)題，于是我們?cè)噲D找到一個(gè)更直接的做法。

設(shè) \(f_k\) 表示一個(gè)長(zhǎng)為 \(k\) 的排列不包含任意連續(xù)段，這樣的排列可以作為其兒子排列。依然考慮容斥遞推，其相當(dāng)于是一個(gè)析點(diǎn)且有 \(k\) 個(gè)兒子，設(shè) \(G_{i, j}\) 表示將 \(i\) 個(gè)數(shù)劃分成 \(j\) 個(gè)排列的方案數(shù)，我們簡(jiǎn)單容斥得：

答案是 \(\sum_{i = 3}^n f_iG_{n, i}\)。

注意到邊界沒(méi)有任何貢獻(xiàn)，所以我們可以亂設(shè)一個(gè)，這里設(shè)是 \(f_1 = f_2 = 0\)，方便后面推導(dǎo)，當(dāng)然此時(shí)所有 \(i = 3\) 都可以改成 \(i = 1\)。

很遺憾的是，\(f\) 沒(méi)有特別快速求的辦法，最快的做 \(G\) 也是 \(n^2\log n\)。

但是我們研究一下 \(f\) 的遞推式依然是有意義的：

先補(bǔ)充一下 \(g\) 的生成函數(shù)，設(shè) \(P(x) = \sum_{i \ge 1} i!x^i\) 則生成函數(shù)是：\(1 - \frac 1{1 + P(x)}\)

發(fā)現(xiàn) \(G_{i,j} = [x^i]P(x)^j\)，而 \(2\sum_{j = 1}^{i - 1}g_j(i - j)!\) 可以直接使用遞推式展開(kāi)，所以：

我們發(fā)現(xiàn)左邊形似一個(gè)多項(xiàng)式復(fù)合，將多出的項(xiàng)消掉，就有：

這個(gè)東西一般有奇效，就是比如說(shuō)我們現(xiàn)在就算一個(gè)沒(méi)有限制的，我們直接帶入 \(G\) 得：

即可迅速做，在有限制的也類(lèi)似。當(dāng)然你再推一步就變成之前的單步容斥了，雖然這個(gè)例子很糖，但還是能感受到那股勁的。

一個(gè)正常點(diǎn)的例子是：P7278 純潔憧憬 的 \(n\log^2 n\) 做法，可以直接看 NaCly_Fish 的題解，但她的做法的 \(f\) 初值是 \(f_1 = 1, f_2 = 2\)，雖然最后推到答案函數(shù)就沒(méi)區(qū)別了就是了我不會(huì)拉反。