Hdu 3962 Microgene (AC自動機+矩陣)

Hdu 3962 Microgene (AC自動機+矩陣)

題目大意：

構造一個串使得有兩個以及兩個以上的目標串。長度為L的所有串中有多少個這樣的串。

思路分析：

用所有的數量減去只有1個和沒有目標串的數量就是答案了。

如果數據很小，可以用dp解。dp[i][j][k] 表示長度為i，走到自動機的j，有k個目標串的數量。

轉移便是。

if(j->next[d] ->isword) dp[i+1][j->next][1] += dp[i][j][0].

else dp[i+1][j->next][0]+=dp[i][j][0],dp[i+1][j->next][1] += dp[i][j][1]...

現在長度達到百萬。

所以用矩陣優化。

設自動機的節點數量為idx，那麼就開一個（2*idx，2*idx）的矩陣。

如果i

如果iidx 表示 開始在i的時候沒有目標串，走到j有了一個。

後面同理。。。

那麼構造這個矩陣便是按照上面的dp方程類似構造。

if(j->next[d]->isword)matrix [i][j->next->index+idx]++; 開始的時候沒有，走過來加一個

else matrix [i][j]++,matrix [i+idx][j+idx] 開始的時候沒有，走到j也沒有 和 開始的時候有一個，走到j還是一個。

矩陣的構造是難= =

#include 
#include 
#include 
#include 
#define N 75
using namespace std;

const int mod = 10007;
const char tab = 'a';
const int max_next = 4;
int rev[256];
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[rev[word[i]]]==NULL)
                t->next[rev[word[i]]]=New();
            t=t->next[rev[word[i]]];
        }
        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;
    int 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;iindex;
                if(sa.ac[i].next[j]->isword)
                    origin.data[i][temp+sa.idx]++;
                else
                    origin.data[i][temp]++,origin.data[i+sa.idx][temp+sa.idx]++;
            }
        }
        origin.print();

        origin=origin^L;

        int ans=1;
        int x=4;
        int t=L;
        while(t)
        {
            if(t&1)ans=(ans*x)%mod;
            x=(x*x)%mod;
            t>>=1;
        }
        for(int i=0;i<2*sa.idx;i++)
        {
            ans-=origin.data[0][i];
            ans=(ans+mod)%mod;
        }

        printf("%d\n",ans);
    }
    return 0;
}