自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:51:56，当前版本为作者最后更新于2018-03-21 14:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这种题目套路性还是蛮强的……

如果熟练了之后还是可以很快干掉它的

在做这道题之前可以先去做一发BZOJ1009(是这道题的弱化版)

(然而我连AC自动机都敲挂了……我怎么这么不熟练啊)

计数dp

嗯如果是计数问题还是字符串的话，如果你足够熟练会想到是在有限状态自动机上跑dp，然后完成我们的计数工作，因为dp是一个足够灵活的计数手段(但是比起数学方法来讲肯定就慢了不少)，可以解决许多有复杂限制的计数问题，比如这道题

(什么你不知道什么是有限状态自动机？科普一下好了)

确定性有限状态自动机 (DFA)

这里不想介绍标准定义了，实用一点的话我们可以定义一个DFA是这个东西：

1.有1个开始节点

2.有若干个终止节点

3.有一个转移函数，f(p,c)表示如果在p状态读入一个c字符会转移到哪个状态

或者我们可以采取更加粗暴的定义，一个DFA是一张图，有一个开始节点和若干个终止节点，点没有实际意义，一个边代表一个字符，而且所有点的出边数目都等于字符集大小(比如一般来讲每个点有26个出边)，我们输入一个字符串相当于在图上以开始节点为起点走出一条路径

定义一个字符串可以被DFA识别，当且仅当我们从开始节点出发，走出这个字符串，最后停在了终止节点上

AC自动机拓展

严格来讲我们平时所使用的AC自动机都是AC自动机的弱化版(因为只配备了fail指针)，如果我们要让AC自动机真正成为一个自动机，那么我们需要强化这个自动机的功能，一般来讲我们称这个东西叫trie图(但是其实trie图就是一个DFA)

如何构建trie图我这里默认大家都会了……(不会出门左转你站膜板区，包教包会)

trie图的功能是，一个字符串可以被识别，当且仅当这个字符串是一堆模式串中的一个，如果这个字符串被输入之后状态不是开始状态也不是结束状态，那么这个串的一个后缀是某个模式串的前缀

做这道题的话性质1就够使了

我们开始考虑dp，当然首先我们先对所有的禁忌词汇建一个trie图，现在我们要构造一个长度为l的串使得这个串的任意一个前缀都不可以被trie图识别，然后对这个串计数

那么我们可以dp啊，设$dp_{i,j}$表示决策到了第i个字符，到达trie图上编号为j的节点的方案数

由于我们每次必须选择一个整单词，所以我们刷表枚举每一个可行的dp状态进行拓展，转移的时候枚举选哪一个单词，然后如果这个单词在跑的过程中都没有经过一个结束节点，那么我们就可以转移，否则不行，假设我们到达了p节点，那么 $dp_{i+len,p}+=dp_{i,j}$就可以了

然后我们发现这是一个$O(n^{3})$的优美算法，显然通过不了$l=10^{8}$的鬼畜数据，但是似乎有特殊性质，所有单词的长度小于2……

由于除了矩阵快速幂我们没有任何可以通过$10^{8}$的算法(根号算法和什么$O(n^{\frac{2}{3}})$估计和计数也没多大关系)，因此我们考虑构造矩阵加速dp

矩阵快速幂优化dp

这应该是一个比较传统的技巧了，熟练的话可以直接看下面的构造矩阵部分

嗯这里默认你会矩阵乘法，不会的话去问度娘好了

我们观察一下矩阵乘法的式子(如果矩阵A乘矩阵B等于矩阵C,而且是两个方阵相乘)

$C_{i,j}=\sum_{k=1}^{n}A_{i,k}B_{k,j}$

我们可以改写成这样的样式

if(a[i][j]!=0)
{
	for(int k=1;k<=n;k++){c[i][k]+=a[i][j]*b[j][k]}
}

是不是非常像dp的状态转移方程?

如果我仅令矩阵的第1行有值的话，那么我们可以得到这样一段代码

if(a[1][j]!=0)
{
	for(int k=1;k<=n;k++){c[1][k]+=a[1][j]*b[j][k]}
}

此时a,c均可以认为是1维数组，也就和平常滚动数组优化之后的dp数组无异

我们发现b矩阵其实是一个转移表格，$b_{i,j}$是否为0代表着i状态是否不可以转移到j状态，

所以我们发现如果处理出各个状态的转移关系并用矩阵存储，每乘一次相当于做了一次转移(也就是滚动数组中的i++)如果要转移n次就相当于计算b矩阵的n次幂再和初始条件相乘，但是i次幂是可以快速幂计算的因此复杂度被优化到了$O(k^{3}logn)$

上面说了这么多只是想说一句话，矩阵快速幂当中，转移矩阵的构造原则是：

如果i可以转移到j那么$b_{i,j}++$

但是我们发现这道题目十分的辣手，单词长度是2而不是1

这意味着我们没办法简单的把dp式子拿过来构造转移矩阵（如果是一个的话每次字符串长度+1因此可以直接枚举每个状态使用什么字母转移来连边，但是两个的话每次字符串长度+1和+2没法一起转移）

因此我们考虑在矩阵快速幂的经典应用——求Fibonacci数列第n项的时候，我们的一个矩阵里存了两个数，$f_{n}$和$f_{n+1}$为的就是每次可以愉快的递推

所以我们的矩阵里也可以不只放一个i啊，我们可以放两个i啊

具体来讲，假设我们现在是用转移矩阵做暴力乘法转移，那么我们被乘的那个1*n的矩阵不再是1*n了，而是1*2n假设已经乘了p次，那么前半段表示$dp_{p-1}$那一行的值，后半段表示$dp_{p}$那一行的值，乘完之后我们希望前半段变成$dp_{p}$，后半段变成$dp_{p+1}$

那么我们可以像这样构造矩阵

tips：我们在处理转移关系的时候把列看成转移前，行看成转移后来连边，乘法操作相当于把这个dp数组转了90度，所以大概是这样~

然后我们根据这个转移关系就可以矩阵快速幂求出答案啦~

这里有一个坑，结束节点的判定需要在trie图的构建中递推的计算，

$end_{p}=end_{p}||end_{failp}$，如果你不明不白的WA了多半是因为这个

(最后由于常数过大尴尬的T飞了~，开了unsigned long long 才过)

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=110;typedef unsigned long long ll;
int n;int m;int l;int siz;ll mod=1e9+7;ll tp[2*N][2*N];
struct mar//矩阵类 
{
    ll m[2*N][2*N];
    void operator *=(const mar& a)
    {
    	for(int i=1;i<=2*siz;i++){for(int j=1;j<=2*siz;j++){tp[i][j]=0;}}
        for(int i=1;i<=2*siz;i++)
        {
            for(int j=1;j<=2*siz;j++)
            {for(int k=1;k<=2*siz;k++){tp[i][j]=(tp[i][j]+m[i][k]*a.m[k][j])%mod;}}
        }
        for(int i=1;i<=2*siz;i++){for(int j=1;j<=2*siz;j++){m[i][j]=tp[i][j];}}
    }
}st,r,tr;
struct trie//trie图 
{
    int mp[N][30];int fil[N];bool ed[N];int cnt;queue <int> q;trie(){cnt=1;}
    inline int add(int p,int c){return mp[p][c]=(mp[p][c])?mp[p][c]:++cnt;}
    inline void end(int p){ed[p]=true;}
    inline void build()//建图函数 
    {
        for(int i=1;i<=26;i++)
        {if(mp[1][i]){q.push(mp[1][i]);fil[mp[1][i]]=1;}else {mp[1][i]=1;}}
        for(;!q.empty();q.pop())//bfs 
        {
            for(int p=q.front(),i=1;i<=26;i++)
            {
                if(mp[p][i])
				{
					q.push(mp[p][i]);fil[mp[p][i]]=mp[fil[p]][i];//连边 
					ed[mp[p][i]]=ed[mp[p][i]]||ed[fil[mp[p][i]]];//记得递推结束标记 
				}
                else {mp[p][i]=mp[fil[p]][i];}
            }
        }
    }
    inline void trv(int& p,int c){p=(ed[mp[p][c]])?-1:mp[p][c];}//转移函数 
}t;
char mde[N][N];int len[N];int dp[N][N];char rd[N];ll res;
int main()
{
    scanf("%d%d%d",&n,&m,&l);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",mde[i]+1);//暴力计算len 
        for(len[i]=1;mde[i][len[i]+1]!='\0';len[i]++);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",rd+1);int p=1;
        for(int i=1;rd[i]!='\0';i++){p=t.add(p,rd[i]-'a'+1);}t.end(p);
    }t.build();siz=t.cnt;
    if(l<=100)//判下l 
    {
        dp[0][1]=1;
        for(int i=0;i<=l;i++)
        {
            for(int j=1;j<=siz;j++)
            {
                if(dp[i][j]==0){continue;}
                for(int k=1;k<=n;k++)
                {
                    if(i+len[k]>l){continue;}int p=j;//判一下转移是否合法 
                    for(int q=1;q<=len[k]&&p!=-1;q++){t.trv(p,mde[k][q]-'a'+1);}
                    if(p!=-1){dp[i+len[k]][p]=(dp[i+len[k]][p]+dp[i][j])%mod;}
                }
            }
        }
        for(int i=1;i<=siz;i++){res=(res+dp[l][i])%mod;}printf("%lld",res);
    }
    else 
    {
        st.m[1][siz+1]=1;//我们从第-1项和第0项开始dp 
        for(int i=1;i<=siz;i++){tr.m[siz+i][i]=1;}//左下方的单位矩阵 
        for(int i=1;i<=siz;i++)
        {
            for(int q=1;q<=n;q++)
            {
                if(len[q]!=1)continue;int p=i;if(t.ed[p])continue;//一步的矩阵 
                t.trv(p,mde[q][1]-'a'+1);if(p!=-1){tr.m[siz+i][siz+p]++;}
            }
        }
        for(int i=1;i<=siz;i++)
        {
            for(int q=1;q<=n;q++)
            {
                if(len[q]!=2)continue;int p=i;if(t.ed[p])continue;
                t.trv(p,mde[q][1]-'a'+1);if(p==-1)continue;//两步的矩阵 
                t.trv(p,mde[q][2]-'a'+1);if(p!=-1){tr.m[i][siz+p]++;}
            }
        }
        for(int i=1;i<=2*siz;i++){r.m[i][i]=1;}//单位元 
        for(int p=l;p;p>>=1,tr*=tr){if(p&1){r*=tr;}}st*=r;//矩阵快速幂 
		for(int i=1;i<=siz;i++){res=(res+st.m[1][siz+i])%mod;}//最后答案是在后边 
        printf("%lld",res); 
    }return 0;//拜拜程序~ 
}