HDU2243_考研路茫茫――单词情结

给出一些词根，问你有多少种长度为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 ;

}