题解 P3715 【[BJOI2017]魔法咒语】
oscar
2017-08-31 11:36:21
北京省选题的日常就是对数据分类讨论。。。
题目瞪一两眼就能看出是道考AC自动机的题
先看前60%数据，发现没有什么特殊要求，且L比较小
直接考虑dp，对“忌讳词语”建一个AC自动机，然后搞出dp方程：
```cpp
if(tmp) dp[i+len[j]][tmp]=(dp[i][id]+dp[i+len[j]][tmp])%(1e9+7);
```
其中i为dp到第几个字符，
tmp为在AC自动机上的第id个点开始，匹配第j个基本词汇后到达的状态，若在匹配过程中遇到“忌讳词语”则不进行转移，
len[j]为第j个基本词汇的长度
最终答案为 $ \sum_{id}{dp[L][id]} mod 10^9+7 $
再考虑第7~8个点，基本词汇长度为1
发现L比较大，可以考虑矩阵快速幂
考虑自动机上每一个节点x，以及从这个节点开始匹配第i个基本词汇达到状态y
这说明从第x个状态长度增加1时可以转移到第y个状态，所以将转移矩阵的第x行第y列+1
这样就解决了
最后两个点基本词汇长度为2
我们只需要把矩阵扩大到原来的两倍，并且按之前的方法在上面标记一下长度为2的基本词汇可以转移到什么位置，然后将矩阵的左下部分设为单位矩阵，就可以解决剩下的数据了
还有一点小细节，矩阵快速幂写得不好可能会导致RE，原因玄学。。
~~下面的代码是考场代码，可能写得有点不优美，大家凑活着看吧。。~~
贴代码~~走人~~
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node
{
int id,end;
node *next[26],*fail;
}*root,pool[30001];
int top;
string bas[55],ban[55];
int n,m,l,len[111],N;long long ans;
int dp[111][111];//[len][id]
const long long mod=1000000007ll;
struct matrix
{
int siz;
int mat[233][233];
#define int long long
matrix(int x=0)
{
siz=N;
for(int i=1;i<=siz;i++)
for(int j=1;j<=siz;j++)
{
mat[i][j]=x*(int)(i==j);
}
}
matrix operator=(const matrix& m)
{
siz=N;
for(int i=1;i<=siz;i++)
{
for(int j=1;j<=siz;j++)
{
mat[i][j]=m.mat[i][j];
}
}
return *this;
}
matrix operator=(const int x)
{
siz=N;
for(int i=1;i<=siz;i++)
for(int j=1;j<=siz;j++)
{
mat[i][j]=x*(int)(i==j);
}
return *this;
}
matrix operator*=(const matrix &m)
{
matrix tmp;
for(int i=1;i<=siz;i++)
{
for(int j=1;j<=siz;j++)
{
long long o=0;
for(int k=1;k<=siz;k++)
{
o+=((long long)mat[i][k]*m.mat[k][j])%mod;
}
o%=mod;
tmp.mat[i][j]=o;
}
}
return *this=tmp;
}
};
inline matrix fexp(matrix &x,int y)
{
int bit=1<<30;
matrix cur=1;
while(bit)
{
cur*=cur;
if(y&bit)cur*=x;
bit>>=1;
}
return cur;
}
#undef int
void addword(string str)
{
int len=str.length();
node *tmp=root;
for(int i=0;i<len;i++)
{
int cur=str[i]-'a';
if(!tmp->next[cur])
{
tmp->next[cur]=&pool[++top];
tmp->next[cur]->id=top;
}
tmp=tmp->next[cur];
}
tmp->end=1;
}
queue<node*> q;
void build()
{
while(!q.empty())q.pop();
q.push(root);
while(!q.empty())
{
node *cur=q.front();q.pop();
for(int i=0;i<26;i++)
{
node *nex=cur->next[i],*tmp=cur->fail;
if(!nex)continue;
while(tmp!=root&&!(tmp->next[i]))tmp=tmp->fail;
if(cur==root||!(tmp->next[i]))
nex->fail=tmp;
else
nex->fail=tmp->next[i];
q.push(nex);
}
}
}
int match(string str,int len,int start)
{
node *cur=&pool[start],*tmp;
for(int i=0;i<len;i++)
{
int e=str[i]-'a';
while(cur!=root&&!(cur->next[e]))cur=cur->fail;
if(cur->next[e])
cur=cur->next[e];
tmp=cur;
while(tmp!=root)
{
if(tmp->end)return 0;
tmp=tmp->fail;
}
}
return cur->id;
}
int main()
{
char buf[110];
root=&pool[++top];root->id=1;root->fail=root;
//#ifndef DDDDBUG
// freopen("sorcery.in","r",stdin);
// freopen("sorcery.out","w",stdout);
//#endif //DDDDBUG
scanf("%d%d%d",&n,&m,&l);
for(int i=1;i<=n;i++)
{
scanf("%s",buf);
bas[i]=buf;
len[i]=bas[i].length();
}
for(int i=1;i<=m;i++)
{
scanf("%s",buf);
ban[i]=buf;
addword(ban[i]);
}
build();
if(l<=100)
{
dp[0][1]=1;
for(int i=0;i<l;i++)
{
for(int j=1;j<=n;j++)
{
if(i+len[j]<=l)
for(int id=1;id<=top;id++)
{
int tmp=match(bas[j],len[j],id);
if(tmp)
dp[i+len[j]][tmp]=(dp[i][id]+dp[i+len[j]][tmp])%mod;
}
}
}
for(int id=1;id<=top;id++)
{
ans=(ans+dp[l][id])%mod;
}
printf("%lld\n",ans);
}
else
{
int notwo=1;
N=2*top;
matrix mult=0;
for(int i=1;i<=top;i++)
{
mult.mat[i+top][i]=1;
}
for(int pos=1;pos<=top;pos++)
{
for(int i=1;i<=n;i++)
{
if(len[i]==1)
{
int x=pos,y=match(bas[i],1,pos);
if(y)
{
mult.mat[x][y]++;
//mult.mat[x+top][y+top]++;//这里我第一次写挂了，去掉就能AC
}
}
else
{
int x=pos,y=match(bas[i],2,pos);
if(y)
mult.mat[x][y+top]++;
notwo=0;
}
}
}
if(notwo)N>>=1;
matrix tmp=fexp(mult,l);
matrix orig=0;
orig.mat[1][1]=1;
orig*=tmp;
for(int pos=1;pos<=top;pos++)
{
ans+=orig.mat[1][pos];
ans%=mod;
}
printf("%lld\n",ans);
}
return 0;
}
```