bzoj 4861 [Beijing2017]魔法咒语
内容
Description
Chandra 是一个魔法天才。
从一岁时接受火之教会洗礼之后，Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。
直到十四岁，开始学习威力强大的禁咒法术时，Chandra 才遇到了障碍。
根据火之魔法规则，禁咒的构成单位是 N 个基本词汇。施法时只要凝聚精神力，说出一段用这些词语组成的长度恰好等于 L 的语言，就能释放威力超乎想象的火法术。过去的魔法师们总结了几种表达起来最连贯的组合方式，方便施法者以最快语速完成法术。
但具有魔法和语言双重天才的 Chandra 不满足于这几种流传下来的禁咒，因为她可以毫无困难地说出普通人几乎不可能表达的禁咒语句。然而，在实际施法时，Chandra 发现有些自创禁咒念出后不但没有预期效果，反而会使自己的精神力迅速枯竭，十分难受。
这个问题令 Chandra 万分不解。她大量阅读典籍，到处走访魔法学者，并且不顾精神折磨一次又一次尝试新咒语，希望找出问题的答案。
很多年过去了，在一次远古遗迹探险中，Chandra 意外闯进了火之神艾利克斯的不知名神殿。根据岩土特征分析，神殿应该有上万年的历史，这是极其罕见的。Chandra 小心
翼翼地四处探索，沿着魔力流动来到一间密室。她看见密室中央悬浮着一本书籍。在魔法保护下书籍状况完好。精通上古语言的 Chandra 读过此书，终于解开了多年的困惑。
禁咒法术之所以威力强大，是因为咒语借用了火之神艾利克斯的神力。这本书里记载了艾利克斯生平忌讳的 M 个词语，比如情敌的名字、讨厌的植物等等。使用禁咒法术时，如果语言中含有任何忌讳词语，就会触怒神力而失效，施法者也一并遭受惩罚。
例如，若 ”banana” 是唯一的忌讳词语，“an”、”ban”、”analysis” 是基本词汇，禁咒长度须是 11，则“bananalysis” 是无效法术，”analysisban”、”anbanbanban”是两个有效法术。注意：一个基本词汇在禁咒法术中可以出现零次、一次或多次；只要组成方式不同就认为是不同的禁咒法术，即使书写形式相同。
谜题破解，Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。
由于答案可能很大，你只需要输出答案模 1,000,000,007 的结果。
Input
第一行，三个正整数 N, M, L。
接下来 N 行，每行一个只含小写英文字母的字符串，表示一个基本词汇。
接下来 M 行，每行一个只含小写英文字母的字符串，表示一个忌讳词语。
对于60%的数据1<=N,M<=50,L<=100
对于另40%数据基本词汇长度不超过2,L<=10^8
Output
仅一行，一个整数，表示答案（模 10^9+7）。
Sample Input
4 2 10
boom
oo
ooh
bang
ob
mo
Sample Output
14
【样例解释 】
有效的禁咒法术共有 14 种：boom/bang/oo，oo/oo/oo/oo/oo，oo/oo/ooh/ooh，
oo/ooh/oo/ooh， oo/ooh/ooh/oo， ooh/oo/oo/ooh， ooh/oo/ooh/oo，
ooh/ooh/boom， ooh/ooh/oo/oo， ooh/ooh/bang， ooh/bang/ooh，
bang/oo/oo/oo， bang/ooh/ooh， bang/bang/oo。
题解
这个数据范围一看就是强行二合一
l小的话，我们对于所有的禁忌串建个ac自动机，记录下从每个点往下一个基本串会转移到那个点，然后直接dp就好了。（和前面的一样
l大的话发现基本串的长度小，假如为1的话，就相当于直接转移，建出矩阵就好了，为2的话保存下i-1和i-2的状态（矩阵大小*2就可以dp了
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 110
#define mod 1000000007
using namespace std;
int n,m,l,sz,root,ans,tot,len,ch[N][26],is_end[N],fail[N],la[N],lb[N],to[N][N],f[N][N];
char basic[N][N],avoid[N][N];
void insert(char s[])
{
int len=strlen(s+1),now=root;
for (int i=1;i<=len;now=ch[now][s[i]-'a'],i++)
if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++sz;
is_end[now]=1;
}
void make_fail()
{
queue<int>que;
for (int i=0;i<26;i++)
if (ch[root][i]) que.push(ch[root][i]);
while(!que.empty())
{
int now=que.front();que.pop();
for (int i=0;i<26;i++)
if (ch[now][i])
fail[ch[now][i]]=ch[fail[now]][i],que.push(ch[now][i]),
is_end[ch[now][i]]|=is_end[ch[fail[now]][i]];
else
ch[now][i]=ch[fail[now]][i];
}
}
void work_l_small()
{
f[0][root]=1;
for (int i=0;i<l;i++)
for (int j=0;j<=sz;j++)
if (f[i][j])
for (int k=1;k<=n;k++)
if (to[j][k]!=-1 && lb[k]+i<=l)
(f[i+lb[k]][to[j][k]]+=f[i][j])%=mod;
for (int i=0;i<=sz;i++)
(ans+=f[l][i])%=mod;
printf("%d\n",ans);
}
int mn;
struct matrixs
{
int m[210][210];
void clear(){memset(m,0,sizeof m);}
matrixs operator * (const matrixs &a) const
{
matrixs ans={};
for (int i=0;i<=mn;i++)
for (int k=0;k<=mn;k++)
if (m[i][k])
for (int j=0;j<=mn;j++)
ans.m[i][j]=(ans.m[i][j]+(long long)m[i][k]*a.m[k][j])%mod;
return ans;
}
matrixs matrix_pow(long long p)
{
matrixs ans,a=(*this);ans.clear();
for (int i=0;i<=mn;i++) ans.m[i][i]=1;
for (;p;a=a*a,p>>=1)
if (p&1) ans=ans*a;
return ans;
}
};
void work_l_large()
{
matrixs m;
mn=sz*2+1;
for (int i=0;i<=sz;m.m[i][i+sz+1]++,i++)
for (int j=1;j<=n;j++)
if (to[i][j]!=-1)
if (strlen(basic[j]+1)==1)
m.m[i][to[i][j]]++;
else
m.m[i+sz+1][to[i][j]]++;
matrixs an=m.matrix_pow(l);
for (int i=0;i<=sz;i++)
(ans+=an.m[0][i])%=mod;
printf("%d\n",ans);
}
main()
{
scanf("%d%d%d",&n,&m,&l);
for (int i=1;i<=n;i++)
scanf("%s",basic[i]+1),lb[i]=strlen(basic[i]+1);
for (int i=1;i<=m;i++)
scanf("%s",avoid[i]+1),la[i]=strlen(avoid[i]+1);
for (int i=1;i<=m;i++)
insert(avoid[i]);
make_fail();
for (int i=0;i<=sz;i++)
for (int j=1;j<=n;j++)
{
int len=strlen(basic[j]+1),now=i,k=1;
for (;k<=len && !is_end[now];now=ch[now][basic[j][k]-'a'],k++);
if (is_end[now]){to[i][j]=-1;continue;}
if (k==len+1) to[i][j]=now;
else to[i][j]=-1;
}
if (l<=100)
work_l_small();
else
work_l_large();
}