HDU 4878 ZCC loves words（AC自动机 + dp + 矩阵快速幂 + 中国剩余定理）

大致题意：给你一些匹配串和一个很长的长度L。让你计算所有长度为L的小写字母构成的字符串的得分总和对5047621取模后的数值。这里，每个字符串s的得分定义为，若s的子串s[i..j]等于第k个匹配串，那么产生p[k]*(len[k]+j)的得分，最后的得分为每一次得分的积。

由于涉及到匹配的问题，所以很自然的可以想到用上AC自动机。我们考虑AC自动机上的dp，我们令dp[l][x]表示长度为l的字符串且当前走到自动机上的x节点时的得分总和。这里我们定义我们的字符串每次是往左边增加一个字符，也即是字符串是倒着变长的。为什么要这么做呢？因为我们注意到得分的定义其实是跟后缀有关的，每在右边增加一个字符，所有的后缀都变了，转移起来就很麻烦。因此不妨反过来考虑，每次在左边增加一个字符。如此，对于点x，假设它的某一个字母a方向的分支为y，那么从y转移过来的代价就是y处以及其fail指针指向的所有匹配串的得分。

我们可以有以下的转移方程：

知道了dp转移的方式和方向，但是实际上我们不能直接这么做，因为这个长度最大可以到1e17。不过，注意到所有匹配串的长度最多不超过40，也即AC自动机的节点个数最多不会超过40。我们可考虑用矩阵快速幂来加速，但是看到我们的转移方程中有当前长度l，不能够直接快速幂。快速幂要求任意几次的转移是一样的。