哎哟喂。中文题。

。

。不说题意了。

首先做过POJ 2778能够知道AC自己主动机是能够求出长度为L的串中不含病毒串的数量的。

POJ 2778的大概思路就是先用全部给的病毒串建一个AC自己主动机。然后将AC自己主动机上全部非单词节点连一个边。

离散数学中有说道。假设矩阵A 中的 [i][j] 表示 i节点通过一条边能够走到j节点的方法数。

那么A*A这个矩阵的[i][j]就表示 i 节点到j 节点通过两条边能够走到j节点的方法数。

既然知道这种方法。我们就明白要求什么。

ans= 26+26^2+26^3+....+26^L - 长度为1不含病毒串的数量-长度为2不含病毒串的数量-...-长度为L不含病毒串的数量。

解决两个问题

对 2^64取模。知道2^64是 long long 的最大值，那么我们直接开成unsigned long long ...然后放心大胆的运算，溢出便是取模。

我们知道矩阵 matrix ^ L 可是要求出全部的和。就要用矩阵里套矩阵。也就是求矩阵的和。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#define N 35

using namespace std;

typedef unsigned long long ll;

const char tab = 'a';

const int max_next = 26;

struct trie

{

    struct trie *fail;

    struct trie *next[max_next];

    int isword;

    int index;

};

struct AC

{

    trie *que[100005],*root,ac[100005];

    int head,tail;

    int idx;

    trie *New()

    {

        trie *temp=&ac[idx];

        for(int i=0;i<max_next;i++)temp->next[i]=NULL;

        temp->fail=NULL;

        temp->isword=0;

        temp->index=idx++;

        return temp;

    }

    void init()

    {

        idx=0;

        root=New();

    }

    void Insert(trie *root,char *word,int len){

        trie *t=root;

        for(int i=0;i<len;i++){

            if(t->next[word[i]-tab]==NULL)

                t->next[word[i]-tab]=New();

            t=t->next[word[i]-tab];

        }

        t->isword++;

    }

    void acbuild(trie *root){

        int head=0,tail=0;

        que[tail++]=root;

        root->fail=NULL;

        while(head<tail){

            trie *temp=que[head++],*p;

            for(int i=0;i<max_next;i++){

                 if(temp->next[i]){

                    if(temp==root)temp->next[i]->fail=root;

                    else {

                        p=temp->fail;

                        while(p!=NULL){

                            if(p->next[i]){

                                temp->next[i]->fail=p->next[i];

                                break;

                            }

                            p=p->fail;

                        }

                        if(p==NULL)temp->next[i]->fail=root;

                    }

                    if(temp->next[i]->fail->isword)temp->next[i]->isword++;

                    que[tail++]=temp->next[i];

                 }

                 else if(temp==root)temp->next[i]=root;

                 else temp->next[i]=temp->fail->next[i];

            }

        }

    }

    void tra()

    {

        for(int i=0;i<idx;i++)

        {

            if(ac[i].fail!=NULL)printf("fail = %d ",ac[i].fail->index);

            for(int k=0;k<max_next;k++)

                printf("%d ",ac[i].next[k]->index);

            puts("");

        }

    }

}sa;

struct matrix

{

    int r,c;

    ll data[N][N];

    matrix(){}

    matrix(int _r,int _c):r(_r),c(_c){memset(data,0,sizeof data);}

    friend matrix operator * (const matrix A,const matrix B)

    {

        matrix res;

        res.r=A.r;res.c=B.c;

        memset(res.data,0,sizeof res.data);

        for(int i=0;i<A.r;i++)

        {

            for(int j=0;j<B.c;j++)

            {

                for(int k=0;k<A.c;k++)

                {

                    if(A.data[i][k] && B.data[k][j]){

                        res.data[i][j]+=A.data[i][k]*B.data[k][j];

                        //res.data[i][j]%=mod;

                    }

                }

            }

        }

        return res;

    }

    friend matrix operator + (const matrix A,const matrix B)

    {

        matrix res;

        res.r=A.r;res.c=A.c;

        memset(res.data,0,sizeof res.data);

        for(int i=0;i<A.r;i++)

        {

            for(int j=0;j<A.c;j++)

            {

                res.data[i][j]=A.data[i][j]+B.data[i][j];

                //res.data[i][j]%=mod;

            }

        }

        return res;

    }

    friend matrix operator - (const matrix A,const matrix B)

    {

        matrix res;

        res.r=A.r;res.c=A.c;

        memset(res.data,0,sizeof res.data);

        for(int i=0;i<A.r;i++)

        {

            for(int j=0;j<A.c;j++)

            {

                res.data[i][j]=A.data[i][j]-B.data[i][j];

                //res.data[i][j]=(res.data[i][j]%mod+mod)%mod;

            }

        }

        return res;

    }

    friend matrix operator ^ (matrix A,int n)

    {

        matrix res;

        res.r=A.r;res.c=A.c;

        memset(res.data,0,sizeof res.data);

        for(int i=0;i<A.r;i++)res.data[i][i]=1;

        while(n)

        {

            if(n&1)res=res*A;

            A=A*A;

            n>>=1;

        }

        return res;

    }

    void print()

    {

        for(int i=0;i<r;i++)

        {

            for(int j=0;j<c;j++)

                printf("%d ",data[i][j]);

            puts("");

        }

    }

}E,zero;

char word[10];

struct supermatrix

{

    matrix ret[2][2];

    friend supermatrix operator * (const supermatrix A,const supermatrix B)

    {

        supermatrix res;

        for(int i=0;i<2;i++)

            for(int j=0;j<2;j++)res.ret[i][j]=zero;

        for(int i=0;i<2;i++)

        {

            for(int j=0;j<2;j++)

            {

                for(int k=0;k<2;k++)

                {

                    res.ret[i][j]=res.ret[i][j]+A.ret[i][k]*B.ret[k][j];

                }

            }

        }

        return res;

    }

    friend supermatrix operator + (const supermatrix A,const supermatrix B)

    {

        supermatrix res;

        for(int i=0;i<2;i++)for(int j=0;j<2;j++)res.ret[i][j]=zero;

        for(int i=0;i<2;i++)

        {

            for(int j=0;j<2;j++)

            {

                res.ret[i][j]=A.ret[i][j]+B.ret[i][j];

            }

        }

        return res;

    }

    friend supermatrix operator ^ (supermatrix A,ll n)

    {

        supermatrix res;

        for(int i=0;i<2;i++)for(int j=0;j<2;j++)res.ret[i][j]=zero;

        for(int i=0;i<2;i++)res.ret[i][i]=E;

        while(n)

        {

            if(n&1)res=res*A;

            A=A*A;

            n>>=1;

        }

        return res;

    }

};

int main()

{

    int n,L;

    while(scanf("%d%d",&n,&L)!=EOF)

    {

        sa.init();

        for(int i=1;i<=n;i++)

        {

            scanf("%s",word);

            sa.Insert(sa.root,word,strlen(word));

        }

        sa.acbuild(sa.root);

        E=matrix(sa.idx,sa.idx);

        for(int i=0;i<N;i++)E.data[i][i]=1;

        zero=matrix(sa.idx,sa.idx);

        matrix origin=matrix(sa.idx,sa.idx);

        for(int i=0;i<sa.idx;i++)

        {

            if(sa.ac[i].isword==0)

            {

                for(int d=0;d<max_next;d++)

                {

                    int temp=sa.ac[i].next[d]->index;

                    if(sa.ac[i].next[d]->isword==0)

                    {

                        origin.data[i][temp]++;

                    }

                }

            }

        }

        supermatrix A;

        A.ret[0][0]=A.ret[0][1]=E;

        A.ret[1][0]=zero;

        A.ret[1][1]=origin;

        A=A^L;

        supermatrix f;

        f.ret[0][0]=f.ret[0][1]=f.ret[1][1]=zero;

        f.ret[1][0]=origin;

        matrix fans=A.ret[0][0]*zero+A.ret[0][1]*origin;

        ll ans=0;

        for(int i=0;i<sa.idx;i++)

        {

            if(sa.ac[i].isword==0)

            {

                ans+=fans.data[0][i];

            }

        }

        matrix I=matrix(2,2);

        I.data[0][0]=I.data[0][1]=1;

        I.data[1][1]=26;

        I.data[1][0]=0;

        I=I^L;

        printf("%I64u\n",I.data[0][1]*26-ans);

    }

    return 0;

}