HDOJ 2243 대학원 진학 길 막막 - 단어 콤플렉스

   
   
   
   

    
    
    
    2 3
aa ab
1 2
a
   
   
   
   

   
   
   
   

    
    
    
    104
52
   
   
   
   

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef unsigned long long int uLL;
typedef long long int LL;

#pragma comment(linker, "/STACK:102400000,102400000")

/************ac_****************/

const int maxn=55;
int ch[maxn][26],fail[maxn],end[maxn];
int root,sz;
char str[maxn];

int N;
LL L;

int newnode()
{
    memset(ch[sz],-1,sizeof(ch[sz]));
    end[sz++]=0;
    return sz-1;
}

void ac_init()
{
    sz=0;
    root=newnode();
}

void ac_insert(char str[])
{
    int len=strlen(str);
    int now=root;
    for(int i=0;i<len;i++)
    {
        if(ch[now][str[i]-'a']==-1)
            ch[now][str[i]-'a']=newnode();
        now=ch[now][str[i]-'a'];
    }
    end[now]++;
}

void ac_build()
{
    queue<int> q;
    fail[root]=root;
    for(int i=0;i<26;i++)
    {
        if(ch[root][i]==-1)
            ch[root][i]=root;
        else
        {
            fail[ch[root][i]]=root;
            q.push(ch[root][i]);
        }
    }
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        if(end[fail[now]]) end[now]++;
        for(int i=0;i<26;i++)
        {
            if(ch[now][i]==-1)
                ch[now][i]=ch[fail[now]][i];
            else
            {
                fail[ch[now][i]]=ch[fail[now]][i];
                q.push(ch[now][i]);
            }
        }
    }
}

/***********MATRIX***************/

struct MARTRIX
{
    int n;
    uLL martrix[maxn][maxn];

    MARTRIX(int x)
    {
        n=x; memset(martrix,0,sizeof(martrix));
    }

    void getONE()
    {
        for(int i=0;i<n;i++)
            martrix[i][i]=1LL;
    }

    MARTRIX operator * (const MARTRIX & b ) const
    {
        MARTRIX ret(n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                uLL temp=0;
                for(int k=0;k<n;k++)
                {
                    temp+=martrix[i][k]*b.martrix[k][j];
                }
                ret.martrix[i][j]=temp;
            }
        }
        return ret;
    }

    MARTRIX operator + (const MARTRIX & b ) const
    {
        MARTRIX ret(n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                ret.martrix[i][j]=martrix[i][j]+b.martrix[i][j];
            }
        }
        return ret;
    }
};

/***************QuickPow********************/

uLL QuickPOW26(LL k)
{
    uLL ts=26,e=1;
    while(k)
    {
        if(k&1) e=e*ts;
        ts=ts*ts;
        k>>=1LL;
    }
    return e;
}

uLL getSUM26(LL L)
{
    if(L==1LL)
    {
        return 26LL;
    }
    LL half=L/2;
    if(L%2==0)
    {
        return getSUM26(half)*(1LL+QuickPOW26(half));
    }
    else
    {
        return getSUM26(half)*(1LL+QuickPOW26(half))+QuickPOW26(L);
    }
}

MARTRIX QuickPOWmatrix(MARTRIX mt,LL k)
{
    MARTRIX e(mt.n);
    e.getONE();

    while(k)
    {
        if(k&1) e=e*mt;
        mt=mt*mt;
        k>>=1LL;
    }

    return e;
}

MARTRIX getSUMmartrix(MARTRIX mt,LL k)
{
    if(k==1LL) return mt;
    LL half=k/2;
    MARTRIX halfmat=getSUMmartrix(mt,half);
    MARTRIX halfpow=QuickPOWmatrix(mt,half);

    if(k&1)
    {
        return halfmat+halfmat*halfpow+QuickPOWmatrix(mt,k);
    }
    else
    {
        return halfmat+halfmat*halfpow;
    }
}

int main()
{
    while(scanf("%d%I64u",&N,&L)!=EOF)
    {
        ac_init();
        for(int i=0;i<N;i++)
        {
            scanf("%s",str);
            ac_insert(str);
        }
        ac_build();

        MARTRIX mt(sz);
        for(int i=0;i<sz;i++)
        {
            if(end[i]) continue;
            for(int j=0;j<26;j++)
            {
                int p=ch[i][j];
                if(end[p]||end[fail[p]]) continue;
                mt.martrix[i][p]++;
            }
        }

        uLL all=getSUM26(L);

        MARTRIX RS=getSUMmartrix(mt,L);
        uLL jian=0;
        for(int i=0;i<sz;i++)
        {
            jian+=RS.martrix[0][i];
        }

        printf("%I64u
",all-jian);
    }
    return 0;
}