BZOJ 2553: 禁忌 - AC 自動機 + 矩陣快速冪期望 DP

問題描述

給定 n 個模式串，字符串「傷害」定義為其子串劃分中最多包含多少模式串。求長度為 len 的隨機字符串（字符集大小 alphabet）的傷害期望值。

建模

構建 AC 自動機，節點代表匹配狀態。危險節點（輸出模式串）或其 fail 指向危險節點，視為「觸發傷害」，傷害 +1 並回到根節點。
狀態轉移構成馬爾可夫鏈。需計算 len 步後的期望傷害。

矩陣優化

引入虛擬吸收態節點 newNode。危險轉移不直接回根，而是同時連向根和 newNode（邊權 1/alphabet）。newNode 自環權重 1。
轉移矩陣 M 大小 (sz+1)²。M^len 中 [root][newNode] 即為答案。用 long double 保證精度。

複雜度

矩陣乘法 O(sz³ log len)，sz ≤ 總模式串長度 ≤ 110，log len ≤ 30，可行。