作者:越野瘾君子_939 | 来源:互联网 | 2023-05-29 18:53
题意Chandra是一个魔法天才。从一岁时接受火之教会洗礼之后,Chandra就显示出对火元素无与伦比的亲和力,轻而易举地学会种种晦涩难解的法术。这也多亏Chandra有着常人难以企及的
题意
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的结果。
给定n个原串和m个禁忌串,要求用原串集合能拼出的不含禁忌串且长度为L的串的数量。(60%)n,m<=50,L<=100。(40%)原串长度为1或2,L<=10^18。
分析
参照ONION_CYC的题解。
其实题意的数据范围不太清晰,反正开200个点就足够了。
因为要匹配禁忌串,所以对禁忌串集合建立AC自动机,标记禁忌串结尾节点,以及下传到所有能fail到的点(这些点访问到都相当于匹配了禁忌串)。
令\(f[i][j]\)表示匹配到节点\(i\),长度为\(j\)的串的数量,先预处理\(a[i][j]\)表示节点 \(i\) 匹配第 \(j\) 个原串到达的节点编号,那么就有:
\[ f [ a[i][j] ] [ L+len[j] ] += f [ i ] [ L ] \]
以上就是60%数据的做法,对于40%的数据使用矩阵快速幂。
假设原串长度均为1,那么DP的转移如下:
\[ f[i][L]=\sum_{j→i}f[j][L−1] \]
这很容易用一个长度为第一维大小(AC自动机节点数)的矩阵维护转移,第L个列向量就是f[i][L]。
如果原串长度有2,那么再记录L-1即可。
答案矩阵如下:
\[ \left[ \begin{matrix} f[0][L] & f[0][L-1] & \dots & f[i][L] & f[i][L-1] & \dots & f[tot][L] & f[tot][L-1] \end{matrix} \right] \]
构造转移矩阵,考虑转移矩阵的意义,第\(i\)行的元素的含义是由\(f[i][\dots]\)转移,第\(j\)列的元素的含义是转移到\(f[i][\dots]\)。转移矩阵的两个下标\(A[i][j]\)可以看成从\(i\)转移到\(j\)。于是不难构造。
时间复杂度
对于60%的数据,\(O(L * ML *N)\),是25000000。中间的\(ML\)是因为禁忌串长似乎与\(L\)同阶。
对于另40%的数据,\(O\left((2M)^3 \log_2 L\right)\),是26575424.759098898782962555435915。
关于矩阵的问题
原作者的矩阵写法跟我的是反着的,导致WA了几次。
\[ (AB)^T=B^TA^T \]
如果将矩阵转置,左右乘也要倒。
另外算快速幂的时候可以边倍增边算答案。
代码
#include
#define rg register
#define il inline
#define co const
templateil T read()
{
rg T data=0;
rg int w=1;
rg char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
{
data=data*10+ch-'0';
ch=getchar();
}
return data*w;
}
templateil T read(rg T&x)
{
return x=read();
}
typedef long long ll;
co int maxn=5001,mod=1e9+7;
int n,m,L;
char s[51][101],buf[101]; // 101:possible string length
int len[51];
namespace AC
{
int tot;
int ch[maxn][26],val[maxn],fail[maxn],a[maxn][101];
void insert(char s[],int n)
{
int u=0;
for(int i=0;iQ;
for(int i=0;i<26;++i)
if(ch[0][i])
Q.push(ch[0][i]);
while(Q.size())
{
int u=Q.front();Q.pop();
for(int i=0;i<26;++i)
{
if(ch[u][i])
{
fail[ch[u][i]]=ch[fail[u]][i];
Q.push(ch[u][i]);
val[ch[u][i]]|=val[fail[ch[u][i]]];
}
else
ch[u][i]=ch[fail[u]][i];
}
}
memset(a,-1,sizeof a);
for(int k=1;k<=n;++k)
for(int i=0;i<=tot;++i)
{
int u=i;
for(int j=0;j=mod?x-mod:x;
}
int mul(int x,int y)
{
return (ll)x*y%mod;
}
namespace T1
{
using namespace AC;
int f[maxn][101];
void solve()
{
f[0][0]=1;
for(int l=0;l>=1;
}
int ans=0;
for(int i=0;i<=tot;++i)if(!val[i])
ans=add(ans,ANS[0][i*2]);
printf("%d\n",ans);
}
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m),read(L);
for(int i=1;i<=n;++i)
{
scanf("%s",s[i]);
len[i]=strlen(s[i]);
}
for(int i=1;i<=m;++i)
{
scanf("%s",buf);
AC::insert(buf,strlen(buf));
}
AC::build();
if(L<=100)
T1::solve();
else
T2::solve();
return 0;
}