序列計(jì)數(shù)

對(duì)于一個(gè)小寫(xiě)字母的序列每次可以將相鄰兩個(gè)不同的小寫(xiě)字母都變?yōu)槎咧?#xff0c;可以進(jìn)行無(wú)限次這樣的操作，求解可以產(chǎn)生多少種不同的序列。

首先我們不能考慮操作，而是考慮合法序列，顯然最后會(huì)形成若干個(gè)區(qū)間，然后每個(gè)區(qū)間必然是對(duì)應(yīng)了最初的一個(gè)位置，并且需要滿足位置的相對(duì)順序不變，所以問(wèn)題等價(jià)于統(tǒng)計(jì)本質(zhì)不同的滿足相鄰字符不同的子序列個(gè)數(shù)，然后利用組合數(shù)直接計(jì)算。

那么考慮動(dòng)態(tài)規(guī)劃，如果采用求子序列個(gè)數(shù)的dp，發(fā)現(xiàn)無(wú)法很好處理相鄰字符不同，但是如果利用子序列自動(dòng)機(jī)，就很好處理，這樣$d{p}_{i,j}$表示當(dāng)前匹配到i這個(gè)字符，然后長(zhǎng)度為j的方案數(shù)，然后每次$O(26)$刷表法轉(zhuǎn)移，總復(fù)雜度$O(26n^2)$。
這個(gè)方法的核心思路就在于利用了自動(dòng)機(jī)優(yōu)化dp，處理一些難以處理的限制。

注意細(xì)節(jié)：

數(shù)組開(kāi)小了。。。這就是我小數(shù)據(jù)對(duì)拍都過(guò)了，但是大數(shù)據(jù)全WA的原因，我還以為是取模的問(wèn)題。。。

暴力哈希的時(shí)候單模數(shù)比不過(guò)ULL自然溢出，很容易就會(huì)發(fā)生沖突。

考慮正解，只是在原來(lái)的基礎(chǔ)上進(jìn)行優(yōu)化，發(fā)現(xiàn)使用填表法效率更高，每個(gè)點(diǎn)對(duì)應(yīng)的轉(zhuǎn)移是一段區(qū)間，所以可以前綴和優(yōu)化。

總結(jié)

以上是生活随笔為你收集整理的序列计数（动态规划/自动机/前缀和优化）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。