题解 P3715 【[BJOI2017]魔法咒语】

这种题目套路性还是蛮强的…… 如果熟练了之后还是可以很快干掉它的 在做这道题之前可以先去做一发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}$ 我们可以改写成这样的样式 ```C if(a[i][j]!=0) { for(int k=1;k<=n;k++){c[i][k]+=a[i][j]*b[j][k]} } ``` 是不是非常像dp的状态转移方程? 如果我仅令矩阵的第1行有值的话，那么我们可以得到这样一段代码 ```C 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 才过)~~ 上代码~ ```C #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;//拜拜程序~ } ```