给出一些词根,问你有多少种长度为L的串包含至少一个词根。
去年就在敲这个题了,今年才敲出来,还是内牛满面之中。。。
要求包含至少一个的情况,需要求出所有的情况,减去一个都没有的情况就可以了。
对于给出的词根,上自动机。然后我们根据tire图可以得出关系状态转移的矩阵。
显然就是矩阵求和了,通过二分幂解决即可。这些地方都有一些技巧可言的。
一开始没有考虑压缩fail指针,考虑了非法的情况,真是wa出翔了。
召唤代码君:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
typedef unsigned long long ll;
using namespace std; ll n,L;
ll next[][],fail[],tag[],N; struct Mat{
ll a[][];
Mat() { memset(a,,sizeof a); }
Mat operator + (Mat M) const {
Mat tmp;
for (ll i=; i<=n; i++)
for (ll j=; j<=n; j++) tmp.a[i][j]=a[i][j]+M.a[i][j];
return tmp;
}
Mat operator * (Mat M) const {
Mat tmp;
for (ll i=; i<=n; i++)
for (ll j=; j<=n; j++)
for (ll k=; k<=n; k++)
tmp.a[i][j]+=a[i][k]*M.a[k][j];
return tmp;
}
Mat power(ll x)
{
Mat tmp1,tmp2;
for (ll i=; i<=n; i++){
tmp1.a[i][i]=;
for (ll j=; j<=n; j++){
tmp2.a[i][j]=a[i][j];
}
}
while (x){
if (x&) tmp1=tmp1*tmp2;
x>>=,tmp2=tmp2*tmp2;
}
return tmp1;
}
void output(){
for (ll i=; i<=n; i++){
for (ll j=; j<=n; j++) cout<<a[i][j]<<' ';
cout<<endl;
}
}
}; ll add()
{
fail[++N]=,tag[N]=;
for (ll i=; i<; i++) next[N][i]=;
return N;
} void insert(char s[])
{
ll cur=,k;
for (ll i=; s[i]; i++){
k=s[i]-'a';
if (!next[cur][k]) next[cur][k]=add();
cur=next[cur][k];
}
tag[cur]=;
} void AC_build()
{
queue<int> Q;
Q.push();
while (!Q.empty()){
ll cur=Q.front(),child,k;
Q.pop();
for (ll i=; i<; i++){
child=next[cur][i];
if (child){
if (!cur) fail[child]=;
else{
for (k=fail[cur]; k && !next[k][i]; k=fail[k]) ;
fail[child]=next[k][i];
}
Q.push(child);
}
else next[cur][i]=next[fail[cur]][i];
}
}
} ll power(ll x,ll y)
{
ll tot=;
while (y){
if (y&) tot=tot*x;
y>>=,x=x*x;
}
return tot;
} int main()
{
char s[];
while (cin>>n>>L){
N=;
fail[]=tag[]=;
for (ll i=; i<; i++) next[][i]=;
for (ll i=; i<n; i++)
{
scanf("%s",s);
insert(s);
}
AC_build();
for (ll i=; i<=N; i++)
if (tag[fail[i]]) tag[i]=;
n=N;
Mat cur,E,ans;
for (ll i=; i<=n; i++)
for (ll j=; j<; j++){
if (!tag[i] && !tag[next[i][j]]) cur.a[i][next[i][j]]++;
} for (ll i=; i<=n; i++) E.a[i][i]=;
Mat tmp=E;
ll num=,here=;
while (L>){
if (L&) {
ans=ans+tmp*cur.power(L);
num+=here*power(,L);
}
L>>=;
here=here*power(,L)+here;
tmp=tmp*(cur.power(L)+E);
}
for(ll i=; i<=n; i++) num-=ans.a[][i];
cout<<num<<endl;
}
return ;
}