Censored! – POJ 1625(ac自动机+简单dp+高精度运算)

题目大意：首先给一个字符集合，这个集合有N个字符，然后需要一个长度为M的句子，但是据子里面不能包含的串有P个，每个串里面的字符都是有字符集和里面的字符构成的，现在想知道最多能构造多少个不重复的句子。 分析：跟以前做过的那两题差不多，不过这个不让取余….不过考虑到字符长度也不大，最多也就50，所以使用一般的dp也可以。ps.在做高高精度运算的时候输出答案竟然正着输出了….然后就一直WA….确实有些时间没有敲过高精度题目了。 代码如下：==============================================================================================================================

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;const int MAXN = ;
const int oo = 1e9+;char WordList[MAXN];
int MaxSon, Matrix[MAXN][MAXN];struct Ac_Trie
{
    int next[MAXN][MAXN], size;
    int Fail[MAXN], End[MAXN], root;    int newnode()
    {
        memset(next[size], -, sizeof(next[size]));
        Fail[size] = End[size] = false;        return size++;
    }
    void InIt()
    {
        size = ;
        root = newnode();
    }    void Insert(char s[])
    {
        int now = root;        for(int i=; s[i]; i++)
        {
            int k = strchr(WordList, s[i]) - WordList;            if(next[now][k] == -)
                next[now][k] = newnode();
            now = next[now][k];
        }        End[now] = true;
    }    void GetFail()
    {
        queue<int> Q;
        int now = root;        Fail[root] = root;        for(int i=; i<MaxSon; i++)
        {
            if(next[now][i] == -)
                next[now][i] = root;
            else
            {
                Fail[next[now][i]] = root;
                Q.push(next[now][i]);
            }
        }        while(Q.size())
        {
            now = Q.front();
            Q.pop();            for(int i=; i<MaxSon; i++)
            {
                if(next[now][i] == -)
                    next[now][i] = next[Fail[now]][i];
                else
                {
                    Fail[next[now][i]] = next[Fail[now]][i];
                    Q.push(next[now][i]);
                }
            }            End[now] |= End[Fail[now]];
        }
    }
    void GetMatrix()
    {
        memset(Matrix, false, sizeof(Matrix));        for(int i=; i<size; i++)
        for(int k=; k<MaxSon; k++)
        {
            if(!End[next[i][k]] && !End[i])
                Matrix[i][next[i][k]] += ;
        }
    }
};
Ac_Trie ac;void BigNumAdd(int a[], int num, int b[])
{
    for(int i=; i<MAXN; i++)
        b[i] += a[i] * num;    for(int i=; i<MAXN-; i++)
    {
        b[i+] += b[i] / ;
        b[i] %= ;
    }
}int main()
{
    int N, P;    while(scanf("%d%d%d", &MaxSon, &N, &P) != EOF)
    {
        char s[MAXN];
        ac.InIt();        getchar();
        gets(WordList);        while(P--)
        {
            gets(s);
            ac.Insert(s);
        }        ac.GetFail();
        ac.GetMatrix();        int dp[][MAXN][MAXN] = {}, op=;
        dp[][][] = ;
        while(N--)
        {
            memset(dp[op], false, sizeof(dp[op]));            for(int i=; i<ac.size; i++)
            for(int j=; j<ac.size; j++)
            {
                if(Matrix[i][j])
                {///dp[op][j] += dp[op^1][i] * Matrix[i][j];
                    BigNumAdd(dp[op^][i], Matrix[i][j], dp[op][j]);
                }
            }            op ^= ;
        }        int ans[MAXN] = {};        for(int i=; i<ac.size; i++)
            BigNumAdd(dp[op^][i], , ans);        N = MAXN - ;
        while(ans[N] ==  && N > )
            N--;        for(int i=N; i>=; i--)
            printf("%d", ans[i]);
        printf("\n");
    }    return ;
}