P9613 解题报告
Hoks
·
·
题解
前言
比较简单的 ACAM+矩阵优化 dp。
广告：串串博客。
类似题目：
P3502 [POI2010] CHO-Hamsters。
SP1676 GEN - Text Generator。
CF696D Legen...。
P3715 [BJOI2017] 魔法咒语。
最后一题是这题的严格加强版（指加强到你被迫打个暴力）。
（这四个人认为难度单增，这题貌似可以放在最前面？）
思路分析
这个题就很小清新了，因为笔者写过这题的严格加强版。
发现是给定的 q 个串不能出现即为多模匹配，考虑对于这 q 个字符串建出 ACAM，给末尾打上标记，再在 fail 树建出来的时候传一下标记。
然后考虑怎么计算方案数。
由于是计数问题，且 q 不大，直接考虑跑暴力 dp。
套路地设计 dp_{i,j} 表示填了 i 位，在 ACAM 上跑到状态 j 时的方案数。
转移的时候考虑大力，尝试每个字符往下转移。
假设最后返回的状态为 x，那么转移方程式即为：
dp_{i+1,x}=dp_{i,j}
转移的时候记得累加一下和就行了。
最后的答案就是 \sum\limits^{tot}_{i=1}dp_{l,n}。
理由也很简单，最后可能停留在 ACAM 上的任意一个点上。
接着考虑怎么优化，套路的想到把 ACAM 上的一个状态看做一个点，把走 $1$ 步的方案数的邻接矩阵 $base$ 处理出来后 $base^l$ 表示走 $l$ 步的方案数。
那这样的话最后的答案就 $\sum\limits^{tot}_{i=1}res_{0,i},res=base^l$。
构造矩阵时直接每个节点尝试往下匹配就行了，然后判断一下这两个状态是不是都可以走即可。
## 代码
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=210,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int n,m,l,le,ans,mx,len[N],dp[N][N];char s[N][N],t[N];
struct ACAM
{
struct node{int nxt,ed,v[26];}t[N];int tot=0;
inline void insert(char s[],int n)
{
int u=0;
for(int i=1;i<=n;i++){if(!t[u].v[s[i]-'a']) t[u].v[s[i]-'a']=++tot;u=t[u].v[s[i]-'a'];}
t[u].ed=1;
}
inline void build()
{
queue<int>q;
for(int i=0;i<26;i++) if(t[0].v[i]) t[t[0].v[i]].nxt=0,q.push(t[0].v[i]);
while(!q.empty())
{
int u=q.front();q.pop();t[u].ed|=t[t[u].nxt].ed;
for(int i=0;i<26;i++)
if(t[u].v[i]) t[t[u].v[i]].nxt=t[t[u].nxt].v[i],q.push(t[u].v[i]);
else t[u].v[i]=t[t[u].nxt].v[i];
}
}
}ac;
struct Matrix
{
int a[N][N];
Matrix(){memset(a,0,sizeof a);}
};
namespace Fast_IO
{
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read()
{
int x(0),t(1);char fc(getchar());
while(!isdigit(fc)&&fc!=-1){if(fc=='-') t=-1;fc=getchar();}
while(isdigit(fc)&&fc!=-1) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
if(fc==-1) exit(0);return x*t;
}
inline void print(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
inline bool chk(char c) { return !(c>='a'&&c<='z'); }
inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1; }
inline void rd(char s[],int&n)
{
s[++n]=getchar();
while(chk(s[n])) s[n]=getchar();
while(ck(s[n])) s[++n]=getchar();
n--;
}
}
using namespace Fast_IO;
Matrix mul(Matrix x,Matrix y)
{
Matrix res;
for(int i=0;i<=mx;i++)
for(int j=0;j<=mx;j++)
for(int k=0;k<=mx;k++)
{
res.a[i][j]+=x.a[i][k]*y.a[k][j];
res.a[i][j]=res.a[i][j]>=mod?res.a[i][j]%mod:res.a[i][j];
}
return res;
}
inline Matrix ksm(Matrix x,int y)
{
Matrix res;for(int i=0;i<=mx;i++) res.a[i][i]=1;
while(y)
{
if(y&1) res=mul(res,x);
x=mul(x,x);y>>=1;
}
return res;
}
signed main()
{
l=read(),m=read();
for(int i=1;i<=m;i++) read(),le=0,rd(t,le),ac.insert(t,le);
ac.build();Matrix base;mx=ac.tot;
for(int x=0;x<=ac.tot;x++)
for(int i=0;i<26;i++)
{
int v=ac.t[x].v[i];
if(!ac.t[x].ed&&!ac.t[v].ed) base.a[x][v]++;
}
Matrix tt=ksm(base,l),t;t.a[0][0]=1;t=mul(t,tt);
for(int pos=0;pos<=ac.tot;pos++) ans=(ans+t.a[0][pos])%mod;
print(ans);
return 0;
}
```