错的上头了...
这题是DNA的加强版，26^1 +26^2... - A^1-A^2...
先去学了矩阵的等比数列求和，学的是第二种方法，扩大矩阵的方法。剩下就是各种模板，各种套。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define LL unsigned __int64
#define N 100001
int t,trie[N][],que[N],o[N],fail[N];
LL p[][],mat[][];
void CL()
{
memset(trie,-,sizeof(trie));
memset(p,,sizeof(p));
memset(o,,sizeof(o));
t = ;
}
void insert(char *s)
{
int i,root,len;
len = strlen(s);
root = ;
for(i = ; i < len; i ++)
{
if(trie[root][s[i]-'a'] == -)
trie[root][s[i]-'a'] = t ++;
root = trie[root][s[i]-'a'];
}
o[root] = ;
}
void build_ac()
{
int head,tail,front,i;
head = tail = ;
for(i = ; i < ; i ++)
{
if(trie[][i] != -)
{
fail[trie[][i]] = ;
que[tail++] = trie[][i];
}
else
{
trie[][i] = ;
}
}
while(head != tail)
{
front = que[head++];
if(o[fail[front]])
o[front] = ;
for(i = ; i < ; i ++)
{
if(trie[front][i] != -)
{
que[tail++] = trie[front][i];
fail[trie[front][i]] = trie[fail[front]][i];
}
else
{
trie[front][i] = trie[fail[front]][i];
}
}
}
}
void work()
{
int i,j;
for(i = ; i < t; i ++)
{
if(o[i]) continue;
for(j = ; j < ; j ++)
{
if(o[trie[i][j]]) continue;
p[i][trie[i][j]] ++;
}
}
for(i = ; i < t; i ++)
{
p[i][t+i] = p[t+i][t+i] = ;
}
t <<= ;
}
LL qmod(LL n)
{
int i,j,k;
LL c[][],ans = ;
while(n)
{
if(n&)
{
memset(c,,sizeof(c));
for(i = ; i < t; i ++)
{
for(j = ; j < t; j ++)
{
for(k = ; k < t; k ++)
{
c[i][j] += mat[i][k]*p[k][j];
}
}
}
memcpy(mat,c,sizeof(mat));
}
memset(c,,sizeof(c));
for(i = ; i < t; i ++)
{
for(j = ; j < t; j ++)
{
for(k = ; k < t; k ++)
{
c[i][j] += p[i][k]*p[k][j];
}
}
}
memcpy(p,c,sizeof(p));
n >>= ;
}
for(i = t/; i < t; i ++)
{
ans += mat[][i];
}
return ans-;
} LL fastmod(LL a,LL k)
{
LL b = ;
while(k)
{
if(k&)
b = a*b;
a = a*a;
k = k/;
}
return b;
}
LL getnum(LL p,LL k)
{
if (k <= ) return ;
if (k% == )
return ((getnum(p,k/ - ))*(( + fastmod(p,k/ + ))) + fastmod(p,k/));
else
return ((getnum(p,(k + )/ - ))*(( + fastmod(p,(k + )/))));
}
int main()
{
int i,j,m;
LL n;
char ch[];
while(scanf("%d%I64u",&m,&n)!=EOF)
{
CL();
for(i = ; i <= m; i ++)
{
scanf("%s",ch);
insert(ch);
}
build_ac();
work();
for(i = ; i < t; i ++)
{
for(j = ; j < t; j ++)
{
mat[i][j] = (i == j);
}
}
printf("%I64u\n",getnum(,n)--qmod(n+));
}
}