HDU2243

• 传送门：HDU2243

　　让我们考虑本题的一个弱化版本，即求出长度恰好为L的方案数。
　　
　　直接求解是non trival的，我们使用补集转化的思想，即求出长度为L的字符串，其任意位置对应的节点都不危险的方案数，再用$26^L$减去其即可。
　　
　　则显然可以用$f(i,j)$代表目标串的第i位在AC自动机上对应编号为j的节点的方案数，且有$f(i,j)=\sum f(i-1,k) \times p(k,j)$成立，其中$p(i,j)$代表AC自动机的第i个节点转移到第j个节点的方案数。这是trival的。关于这，可以参看POJ2778。
　　

　　但事实上，我们的目标是求出$\sum_{i=1}^{L} 26^i - \sum_{i=1,notdanger(j)}^{L} f(i,j)$，即求出$\sum_{i=1,notdanger(j)}^{L} f(i,j)$，令$G$表示初始矩阵，设$t(i)=G \times p^{i}$ ,很容易发现$f(i,j)=t(i)_j$，于是目标即是要求$\sum_{i=0}^{L-1} \sum_{j=1,notdanger(j)}^{tot} t(i)_j$，将求和换序，即$\sum_{j=1,notdanger(j)}^{tot} \sum_{i=0}^{L-1} t(i)_j$,即$\sum_{j=1,notdanger(j)}^{tot} \sum_{i=0}^{L-1} t(i)$。
　　
　　让我们来观察$\sum t(i)$，事实上，这是一个关于$p$的多项式，即$G\sum_{i=1}^{L-1} p^i$，由Horner's Rule，可以将$\sum p^i$ 改写为$[\sum p^{i-1}] \times p +E$，于是构造矩阵R,其中的元素为两个矩阵:$R=[\sum p^{i-1},E]$，构造转移矩阵T,元素为$T_{1,1}=p,T_{1,2}=0,T_{2,1}=E,T_{2,2}=E$，于是显然，$\sum t(i) =G( [E,E]\times T^{L-1})_{1,1}=G T^{L-1}_{1,1}$。
　　
　　这就完成了题目。