#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn=1000,tot=4;
const ll bign=100000;
struct Node;
struct Matrix;
typedef Node* pNode;
int rank[256],beg;

struct Node
{
    int id;
    int count;
    pNode son[tot],fail;

    Node():id(0),fail(0)
    {
        memset(son,0,sizeof (son));
    }
};
pNode root;

struct Matrix
{
    int size;
    ll unit[102][102];

    ll*operator [](int i)
    {
        return unit[i];
    }

    Matrix():size(0)
    {
        memset(unit,0,sizeof (unit));
    }

    Matrix(int s):size(s)
    {
        memset(unit,0,sizeof (unit));
    }
} ans;

void Init()
{
    beg=1;
    root=new Node;
    root->id=1;
}

void Insert(char str[])
{
    pNode u,v;
    int key;
    for (u=root;key=rank[*str],*str;u=u->son[key],str++)
        if (u->son[key]==0)u->son[key]=new Node,u->son[key]->id=++beg;
    u->count++;
}
pNode que[400];
bool vis[100];

void Build()
{
    pNode u,v,cur;
    int key,fi=0,la=-1;
    root->fail=root;
    for (key=0;key<tot;key++)
        if (v=root->son[key])v->fail=root,que[++la]=v;

    while (fi<=la)
    {
        u=que[fi++];
        for (key=0;key<tot;key++)
        {
            cur=u->fail->son[key];
            if (v=u->son[key])
            {
                que[++la]=v;
                v->fail=(cur)?cur:root;
            } else u->son[key]=cur;
        }
        for (v=u;u->count==0;v=v->fail)
        {
            if (v->count)
            {
                u->count++;
                break;
            }
            if (v==root)break;
        }
    }

    memset(ans.unit,0,sizeof (ans.unit));
    memset(vis,0,sizeof (vis));
    ans.size=beg;
    fi=0,la=-1;
    que[++la]=root;
    vis[root->id]=true;
    while (fi<=la)
    {
        u=que[fi++];
        if (u->count)continue;
        for (key=0;key<tot;key++)
            if (v=u->son[key])
            {
                ans[u->id][v->id]++;
                if (!vis[v->id])que[++la]=v,vis[v->id]=true;
            } else ans[u->id][root->id]++;
    }
}

char tmp[20];

Matrix operator*(Matrix &a,Matrix&b)
{
    Matrix c(a.size);
    for (int i=1;i<=a.size;i++)
        for (int j=1;j<=a.size;j++)
            for (int k=1;k<=a.size;k++)
                c[i][j]=(((a[i][k]%bign)*b[k][j])%bign+c[i][j])%bign;
    return c;
}

Matrix PowerMod(Matrix &a,int t)
{
    Matrix b(a.size);
    for (int i=1;i<=a.size;i++)b[i][i]=1;
    while (t)
    {
        if (t&1)b=b*a;
        a=a*a;
        t>>=1;
    }
    return b;
}

int main()
{
    int n,m;
    rank['A']=0;
    rank['C']=1;
    rank['T']=2;
    rank['G']=3;
    scanf("%d%d",&n,&m);
    Init();
    while (n--)scanf("%s",tmp),Insert(tmp);
    Build();
    ans=PowerMod(ans,m);
    memset(vis,0,sizeof (vis));
    int fi=0,la=-1;
    ll ret=0;
    que[++la]=root;
    vis[root->id]=true;
    while (fi<=la)
    {
        pNode u=que[fi++],v;
        if (u->count)continue;
        ret=(ret+ans[root->id][u->id])%bign;
        for (int key=0;key<tot;key++)
            if ((v=u->son[key])&&!vis[v->id])
                que[++la]=v,vis[v->id]=true;
    }
    printf("%I64d\n",ret);
    return 0;
}

//1. long long used.
//2. The fact that some virus string is the substring of others also be considered.
//3. Do you have any other adivice? Thanks for you help..
//    ______________________________an ACMer in desperate need of your help

• Re:求助wa，老衲过掉了网上能找到的所有数据，并且和很多人的AC代码对拍掉了很多数据， (381) lzqxh 2012-02-16 22:34:26