Hdu 2243 考研路茫茫——單詞情結 （AC自動機+矩陣）

Hdu 2243 考研路茫茫——單詞情結 （AC自動機+矩陣）

哎喲喂，中文題。。。不說題意了。

首先做過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 
#include 
#include 
#include 
#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;inext[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;inext[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(headnext[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;iindex);
            for(int k=0;kindex);
            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>=1;
        }
        return res;
    }
    void print()
    {
        for(int i=0;i>=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;iindex;
                    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