[CTSC2006]歌唱王國

題目

傳送門 to luogu

思路

感謝@xyz32768 的部落格提供了思路。我不生産思考，我隻是智慧結晶的搬運工。

首先，按照一般的做法，設 f x f_x fx​ 表示長度為 x x x 時成功比對的機率； g x g_x gx​ 表示長度為 x x x 時沒有成功比對（長度超過 x x x 時完成比對）的機率。然後就發現做不動了。

怎麼辦呢？使用船新操作：機率生成函數！名字聽着玄乎，其實不好用，而且難點不在這上面。

我們将 F ( x ) = ∑ i = 0 + ∞ E i x i F(x)=\sum_{i=0}^{+\infty}E_ix^i F(x)=∑i=0+∞​Ei​xi 稱為機率生成函數。其中 E i E_i Ei​ 表示檢測值為 i i i 的機率。

将 x = 1 x=1 x=1 代入，得到 F ( 1 ) = ∑ i = 0 + ∞ E i = 1 F(1)=\sum_{i=0}^{+\infty}E_i=1 F(1)=∑i=0+∞​Ei​=1 （萬川東到海，機率和為一）。

對 F F F 求導，得到 F ′ ( x ) = ∑ i = 1 + ∞ i E i x i − 1 F'(x)=\sum_{i=1}^{+\infty}iE_{i}x^{i-1} F′(x)=∑i=1+∞​iEi​xi−1 ；于是将 x = 1 x=1 x=1 代入，得到 F ′ ( 1 ) = ∑ i = 1 + ∞ i E i = e F'(1)=\sum_{i=1}^{+\infty}iE_i=e F′(1)=∑i=1+∞​iEi​=e （即原本要求的期望值）。

說了這麼多，我們回到這道題，考慮這兩個生成函數：

• f f f 的生成函數 F ( x ) = ∑ i = 0 + ∞ f i x i F(x)=\sum_{i=0}^{+\infty}f_i x^i F(x)=∑i=0+∞​fi​xi
• g g g 的生成函數 G ( x ) = ∑ i = 0 + ∞ g i x i G(x)=\sum_{i=0}^{+\infty}g_i x^i G(x)=∑i=0+∞​gi​xi

我們要找他們之間的關系，可以找 f f f 和 g g g 之間的關系。

關系一

g i = f i + 1 + g i + 1 g_i=f_{i+1}+g_{i+1} gi​=fi+1​+gi+1​

這是當然咯，長度為 i i i 時沒有比對，那就是長度為 i + 1 i+1 i+1 時比對，或者比 i + 1 i+1 i+1 更長的時候比對。

我們試着用生成函數的形式寫出來：

F ( x ) = f 0 + f 1 x + f 2 x 2 + ⋯ + f n x n + ⋯ G ( x ) = g 0 + g 1 x + g 2 x 2 + ⋯ + g n x n + ⋯ x G ( x ) = g 0 x + g 1 x 2 + ⋯ + g n − 1 x n + ⋯ \begin{aligned} F(x)&=f_0+f_1x+f_2x^2+\cdots+f_nx^n+\cdots\\ G(x)&=g_0+g_1x+g_2x^2+\cdots+g_nx^n+\cdots\\ xG(x)&=\qquad g_0x+g_1x^2+\cdots+g_{n-1}x^n+\cdots \end{aligned} F(x)G(x)xG(x)​=f0​+f1​x+f2​x2+⋯+fn​xn+⋯=g0​+g1​x+g2​x2+⋯+gn​xn+⋯=g0​x+g1​x2+⋯+gn−1​xn+⋯​

加之 f 0 = 0 , g 0 = 1 f_0=0,g_0=1 f0​=0,g0​=1 ，顯然， x G ( x ) = F ( x ) + G ( x ) − 1 (1) xG(x)=F(x)+G(x)-1\tag{1} xG(x)=F(x)+G(x)−1(1)

盡管 ( 1 ) (1) (1) 式目前沒有什麼用，等會兒我們會看到它的功力。雖然那個結論不用生成函數也能證。

關系二（不易發現）

用 L L L 表示原字元串的長度， m m m 表示字元集（生成時是每次在 [ 1 , m ] [1,m] [1,m] 中随機一個整數）大小，則

( 1 m ) L ⋅ g x = ∑ i = 1 L a i ( 1 m ) L − i ⋅ f x + i \left(\frac{1}{m}\right)^L\cdot g_x = \sum_{i=1}^{L}a_i\left(\frac{1}{m}\right)^{L-i}\cdot f_{x+i} (m1​)L⋅gx​=i=1∑L​ai​(m1​)L−i⋅fx+i​

a i a_i ai​ 表示，原字元串的前 i i i 位和後 i i i 位是否相同。相同為 1 1 1 ，否則為 0 0 0 。即，原字元串是否有一個長度為 i i i 的 b o r d e r \rm border border 。為啥有這個式子成立呢？

首先， f f f 表示的已經比對的字元串，一定是 以原字元串結尾。也就是說，最後 L L L 個字元一定就是原字元串。而且，去掉最後一個字元，一定沒有完成比對。

看右邊的式子。 a i = 1 a_i=1 ai​=1 時才會累加，這就代表着原字元串前 i i i 個字元與後 i i i 個字元相同。而 f i + x f_{i+x} fi+x​ 就是以原字元串結尾的。是以 f i + x f_{i+x} fi+x​ 的後 i i i 位，恰好就是原字元串的後 i i i 位，與原字元串的前 i i i 位相同。此時，在末尾接上一截剩下的 L − i L-i L−i 位，最後 L L L 位就恰好比對了。 I n    o t h e r    w o r d s \rm In\;other\;words Inotherwords ，我們完成了一個長度為 x + L x+L x+L 的比對于尾端，但是隻能保證前 x x x 位沒有比對。

對于左式，很簡單，對于一個長度為 x x x 的、尚未完成比對的字元串，我在後面暴力接入了一個原字元串。兩式都代表一個長度為 x + L x+L x+L 的已經比對的字元串，故相等。

其實，右式就是在枚舉：将原字元串的前 i i i 位接到最後，就已經完成了比對。

我們再用生成函數的方法寫出來：

( x m ) L G ( x ) = ∑ i = 0 + ∞ ( 1 m ) L g i x i + L F ( x ) ∑ i = 1 L a i ( x m ) L − i = ∑ i = 0 + ∞ x i + L ∑ j = 1 L a j ( 1 m ) L − j f i + j \begin{aligned} \left(\frac{x}{m}\right)^L G(x)&=\sum_{i=0}^{+\infty}\left(\frac{1}{m}\right)^Lg_ix^{i+L}\\ F(x)\sum_{i=1}^{L}a_i\left(\frac{x}{m}\right)^{L-i}&=\sum_{i=0}^{+\infty}x^{i+L}\sum_{j=1}^{L}a_j\left(\frac{1}{m}\right)^{L-j}f_{i+j} \end{aligned} (mx​)LG(x)F(x)i=1∑L​ai​(mx​)L−i​=i=0∑+∞​(m1​)Lgi​xi+L=i=0∑+∞​xi+Lj=1∑L​aj​(m1​)L−jfi+j​​

你可能會問，下面那個等式是怎麼搞出來的？可以考慮 x i + L x^{i+L} xi+L 的系數由什麼組成。假設左式的求和中的 a j ( x m ) L − j a_j(\frac{x}{m})^{L-j} aj​(mx​)L−j 為之提供了貢獻，由于其次數是 L − j L-j L−j ，是以原本 F ( x ) F(x) F(x) 中是 x i + j x^{i+j} xi+j 這一項與之相乘。故 F ( x ) F(x) F(x) 的系數是 f i + j f_{i+j} fi+j​ ，求和中的系數是 a j ( 1 m ) L − j a_j(\frac{1}{m})^{L-j} aj​(m1​)L−j ，相乘即可。

仔細觀察，得到結論： ( x m ) L G ( x ) = F ( x ) ∑ i = 1 L a i ( x m ) L − i (2) \left(\frac{x}{m}\right)^LG(x)=F(x)\sum_{i=1}^L a_i\left(\frac{x}{m}\right)^{L-i}\tag{2} (mx​)LG(x)=F(x)i=1∑L​ai​(mx​)L−i(2)

嗯，好像差不多，該進行體力工作了：暴力解！

對 ( 1 ) (1) (1) 式兩邊求導，有 x G ′ ( x ) + G ( x ) = F ′ ( x ) + G ′ ( x ) xG'(x)+G(x)=F'(x)+G'(x) xG′(x)+G(x)=F′(x)+G′(x)

導數基本姿勢 [ f ( x ) g ( x ) ] ′ = f ′ ( x ) g ( x ) + f ( x ) g ′ ( x ) [f(x)g(x)]'=f'(x)g(x)+f(x)g'(x) [f(x)g(x)]′=f′(x)g(x)+f(x)g′(x) 應該是人盡皆知的吧？

然後你可以移項，得到 F ′ ( x ) = ( x − 1 ) G ′ ( x ) + G ( x ) F'(x)=(x-1)G'(x)+G(x) F′(x)=(x−1)G′(x)+G(x)

F ′ ( x ) F'(x) F′(x) 鳥用沒有，我們想知道的是什麼？在 x = 1 x=1 x=1 處的取值。答案就是 F ′ ( 1 ) F'(1) F′(1) 嘛。我們試試：

F ′ ( 1 ) = ( 1 − 1 ) G ′ ( 1 ) + G ( 1 ) = G ( 1 ) F'(1)=(1-1)G'(1)+G(1)=G(1) F′(1)=(1−1)G′(1)+G(1)=G(1)

這告訴我們， G ( 1 ) G(1) G(1) 就是答案！雖然這個結論不用生成函數也挺顯然的。

( 2 ) (2) (2) 式還沒有使用呢。我們拿出來，發現 G ( x ) G(x) G(x) 也鳥用沒有——我們需要 G ( 1 ) G(1) G(1) 。我們再試一次：

( 1 m ) L G ( 1 ) = F ( 1 ) ∑ i = 1 L a i ( 1 m ) L − i \left(\frac{1}{m}\right)^LG(1)=F(1)\sum_{i=1}^{L}a_i\left(\frac{1}{m}\right)^{L-i} (m1​)LG(1)=F(1)i=1∑L​ai​(m1​)L−i

哦，對了，我一來就說了， F ( 1 ) = 1 F(1)=1 F(1)=1 恒成立。代入如何？

G ( 1 ) = ∑ i = 1 L a i × m i G(1)=\sum_{i=1}^{L}a_i\times m^i G(1)=i=1∑L​ai​×mi

任務完成。 a i a_i ai​ 這種東西，哈希呗！（雖然 k m p \tt kmp kmp 可能更好打。）

代碼

看了看題解，并不長的樣子。然而我還是不想打了。
           

實在想要代碼，去題解區搞一份噻！

後記

K n o w N a m e B l o g e r \sf KnowNameBloger KnowNameBloger 在另一道類似的題目中，試圖在後方加入一個長度為 n − 1 n-1 n−1 的串，然而總是差一項。我也百思不得其解。進行了充分的思考之後，我意識到：

加上長度為 n − 1 n-1 n−1 的串對 g 0 g_0 g0​ 不适用

。是以那種方法求出來的值會小 1 1 1 。