POJ 1625 Censored!（AC自动机+DP+高精度）

Censored!
Time Limit: 5000MS Memory Limit: 10000K
Total Submissions: 10476 Accepted: 2874
Description

The alphabet of Freeland consists of exactly N letters. Each sentence of Freeland language (also known as Freish) consists of exactly M letters without word breaks. So, there exist exactly N^M different Freish sentences.

But after recent election of Mr. Grass Jr. as Freeland president some words offending him were declared unprintable and all sentences containing at least one of them were forbidden. The sentence S contains a word W if W is a substring of S i.e. exists such k >= 1 that S[k] = W[1], S[k+1] = W[2], …,S[k+len(W)-1] = W[len(W)], where k+len(W)-1 <= M and len(W) denotes length of W. Everyone who uses a forbidden sentence is to be put to jail for 10 years.

Find out how many different sentences can be used now by freelanders without risk to be put to jail for using it.
Input

The first line of the input file contains three integer numbers: N — the number of letters in Freish alphabet, M — the length of all Freish sentences and P — the number of forbidden words (1 <= N <= 50, 1 <= M <= 50, 0 <= P <= 10).

The second line contains exactly N different characters — the letters of the Freish alphabet (all with ASCII code greater than 32).

The following P lines contain forbidden words, each not longer than min(M, 10) characters, all containing only letters of Freish alphabet.
Output

Output the only integer number — the number of different sentences freelanders can safely use.
Sample Input

2 3 1
ab
bb
Sample Output

5

题目链接：POJ 1625
一开始没发现是高精度的，WA了几次，加了清华爷的大整数模板重新估计了下空间复杂度，然而还MLE了几次（弱校选手刷个水题战况惨不忍睹，哎），看看$m$这么小想想还是用普通递推型DP吧，怎么DP呢？按套路应该是用$dp[i][j]$表示构造的长度为$i$的字符串，走到了Trie上第$j$个节点，设$v$为$j$的某一个儿子节点，$G$矩阵为记录AC自动机上节点之间是否能转移的邻接矩阵

$$dp[0][0] = 1,\\ dp[i+1][v] += dp[i][j] \mid G[j][v]==1$$

喔据说还有最好用unsigned char作数组，数据可能有ASCII码大于$127$的数据
代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 120;
const int MAX_L = 100;
class bign
{
    public:
        int len, s[MAX_L];
        bign();
        bign(const char*);
        bign(int);
        bool sign;
        string toStr() const;
        friend istream& operator>>(istream &, bign &);
        friend ostream& operator<<(ostream &, bign &);
        bign operator=(const char*);
        bign operator=(int);
        bign operator=(const string);
        bool operator>(const bign &) const;
        bool operator>=(const bign &) const;
        bool operator<(const bign &) const;
        bool operator<=(const bign &) const;
        bool operator==(const bign &) const;
        bool operator!=(const bign &) const;
        bign operator+(const bign &) const;
        bign operator++();
        bign operator++(int);
        bign operator+=(const bign&);
        bign operator-(const bign &) const;
        bign operator--();
        bign operator--(int);
        bign operator-=(const bign&);
        bign operator*(const bign &)const;
        bign operator*(const int num)const;
        bign operator*=(const bign&);
        bign operator/(const bign&)const;
        bign operator/=(const bign&);
        bign operator%(const bign&)const;
        bign factorial()const;
        bign Sqrt()const;
        bign pow(const bign&)const;
        void clean();
        ~bign();
};
bign::bign()
{
    for (int i = 0; i < MAX_L; ++i)
        s[i] = 0;
    len = 1;
    sign = 1;
}

bign::bign(const char *num)
{
    *this = num;
}

bign::bign(int num)
{
    *this = num;
}

string bign::toStr() const
{
    string res;
    res = "";
    for (int i = 0; i < len; i++)
        res = (char)(s[i] + '0') + res;
    if (res == "")
        res = "0";
    if (!sign && res != "0")
        res = "-" + res;
    return res;
}

istream &operator>>(istream &in, bign &num)
{
    string str;
    in >> str;
    num = str;
    return in;
}

ostream &operator<<(ostream &out, bign &num)
{
    out << num.toStr();
    return out;
}

bign bign::operator=(const char *num)
{
    memset(s, 0, sizeof(s));
    char a[MAX_L] = "";
    if (num[0] != '-')
        strcpy(a, num);
    else
        for (int i = 1; i < strlen(num); i++)
            a[i - 1] = num[i];
    sign = !(num[0] == '-');
    len = strlen(a);
    for (int i = 0; i < strlen(a); i++)
        s[i] = a[len - i - 1] - 48;
    return *this;
}

bign bign::operator=(int num)
{
    char temp[MAX_L];
    sprintf(temp, "%d", num);
    *this = temp;
    return *this;
}

bign bign::operator=(const string num)
{
    const char *tmp;
    tmp = num.c_str();
    *this = tmp;
    return *this;
}

bool bign::operator<(const bign &num) const
{
    if (sign ^ num.sign)
        return num.sign;
    if (len != num.len)
        return len < num.len;
    for (int i = len - 1; i >= 0; i--)
        if (s[i] != num.s[i])
            return sign ? (s[i] < num.s[i]) : (!(s[i] < num.s[i]));
    return !sign;
}

bool bign::operator>(const bign&num)const
{
    return num < *this;
}

bool bign::operator<=(const bign&num)const
{
    return !(*this > num);
}

bool bign::operator>=(const bign&num)const
{
    return !(*this < num);
}

bool bign::operator!=(const bign&num)const
{
    return *this > num || *this < num;
}

bool bign::operator==(const bign&num)const
{
    return !(num != *this);
}

bign bign::operator+(const bign &num) const
{
    if (sign ^ num.sign)
    {
        bign tmp = sign ? num : *this;
        tmp.sign = 1;
        return sign ? *this - tmp : num - tmp;
    }
    bign result;
    result.len = 0;
    int temp = 0;
    for (int i = 0; temp || i < (max(len, num.len)); i++)
    {
        int t = s[i] + num.s[i] + temp;
        result.s[result.len++] = t % 10;
        temp = t / 10;
    }
    result.sign = sign;
    return result;
}

bign bign::operator++()
{
    *this = *this + 1;
    return *this;
}

bign bign::operator++(int)
{
    bign old = *this;
    ++(*this);
    return old;
}

bign bign::operator+=(const bign &num)
{
    *this = *this + num;
    return *this;
}

bign bign::operator-(const bign &num) const
{
    bign b = num, a = *this;
    if (!num.sign && !sign)
    {
        b.sign = 1;
        a.sign = 1;
        return b - a;
    }
    if (!b.sign)
    {
        b.sign = 1;
        return a + b;
    }
    if (!a.sign)
    {
        a.sign = 1;
        b = bign(0) - (a + b);
        return b;
    }
    if (a < b)
    {
        bign c = (b - a);
        c.sign = false;
        return c;
    }
    bign result;
    result.len = 0;
    for (int i = 0, g = 0; i < a.len; i++)
    {
        int x = a.s[i] - g;
        if (i < b.len) x -= b.s[i];
        if (x >= 0) g = 0;
        else
        {
            g = 1;
            x += 10;
        }
        result.s[result.len++] = x;
    }
    result.clean();
    return result;
}

bign bign::operator * (const bign &num)const
{
    bign result;
    result.len = len + num.len;

    for (int i = 0; i < len; i++)
        for (int j = 0; j < num.len; j++)
            result.s[i + j] += s[i] * num.s[j];

    for (int i = 0; i < result.len; i++)
    {
        result.s[i + 1] += result.s[i] / 10;
        result.s[i] %= 10;
    }
    result.clean();
    result.sign = !(sign ^ num.sign);
    return result;
}

bign bign::operator*(const int num)const
{
    bign x = num;
    bign z = *this;
    return x * z;
}
bign bign::operator*=(const bign&num)
{
    *this = *this * num;
    return *this;
}

bign bign::operator /(const bign&num)const
{
    bign ans;
    ans.len = len - num.len + 1;
    if (ans.len < 0)
    {
        ans.len = 1;
        return ans;
    }

    bign divisor = *this, divid = num;
    divisor.sign = divid.sign = 1;
    int k = ans.len - 1;
    int j = len - 1;
    while (k >= 0)
    {
        while (divisor.s[j] == 0) j--;
        if (k > j) k = j;
        char z[MAX_L];
        memset(z, 0, sizeof(z));
        for (int i = j; i >= k; i--)
            z[j - i] = divisor.s[i] + '0';
        bign dividend = z;
        if (dividend < divid)
        {
            k--;
            continue;
        }
        int key = 0;
        while (divid * key <= dividend) key++;
        key--;
        ans.s[k] = key;
        bign temp = divid * key;
        for (int i = 0; i < k; i++)
            temp = temp * 10;
        divisor = divisor - temp;
        k--;
    }
    ans.clean();
    ans.sign = !(sign ^ num.sign);
    return ans;
}

bign bign::operator/=(const bign&num)
{
    *this = *this / num;
    return *this;
}

bign bign::operator%(const bign& num)const
{
    bign a = *this, b = num;
    a.sign = b.sign = 1;
    bign result, temp = a / b * b;
    result = a - temp;
    result.sign = sign;
    return result;
}

bign bign::pow(const bign& num)const
{
    bign result = 1;
    for (bign i = 0; i < num; i++)
        result = result * (*this);
    return result;
}

bign bign::factorial()const
{
    bign result = 1;
    for (bign i = 1; i <= *this; i++)
        result *= i;
    return result;
}

void bign::clean()
{
    if (len == 0)
        len++;
    while (len > 1 && s[len - 1] == '\0')
        len--;
}

bign bign::Sqrt()const
{
    if (*this < 0)return -1;
    if (*this <= 1)return *this;
    bign l = 0, r = *this, mid;
    while (r - l > 1)
    {
        mid = (l + r) / 2;
        if (mid * mid > *this)
            r = mid;
        else
            l = mid;
    }
    return l;
}
bign::~bign()
{
}
int n, m, p;
struct Trie
{
    int nxt[50];
    int fail, flag;
    void init()
    {
        for (int i = 0; i < 50; ++i)
            nxt[i] = -1;
        fail = flag = 0;
    }
} L[N];
int sz;
unsigned char str[N];
int order[259];
int G[N][N];
bign dp[N][N];

void init()
{
    CLR(order, -1);
    CLR(G, 0);
    CLR(dp, 0);
}
namespace ac
{
    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    void ins(unsigned char s[], int len)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
            if (order[s[i]] == -1)
                return ;
        for (int i = 0; i < len; ++i)
        {
            int v = order[(int)s[i]];
            if (L[u].nxt[v] == -1)
            {
                L[sz].init();
                L[u].nxt[v] = sz++;
            }
            u = L[u].nxt[v];
        }
        L[u].flag = 1;
    }
    void build()
    {
        L[0].fail = 0;
        queue<int>Q;
        for (int i = 0; i < n; ++i)
        {
            int v = L[0].nxt[i];
            if (~v)
            {
                L[v].fail = 0;
                Q.push(v);
            }
            else
                L[0].nxt[i] = 0;
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            if (L[uf].flag)
                L[u].flag = 1;
            for (int i = 0; i < n; ++i)
            {
                int v = L[u].nxt[i];
                if (~v)
                {
                    L[v].fail = L[uf].nxt[i];
                    Q.push(v);
                }
                else
                    L[u].nxt[i] = L[uf].nxt[i];
            }
        }
    }
}
int main(void)
{
    int i, j, k;
    while (~scanf("%d%d%d", &n, &m, &p))
    {
        init();
        ac::init();
        scanf("%s", str);
        sort(str, str + n);
        for (i = 0; i < n; ++i)
            order[(int)str[i]] = i;
        while (p--)
        {
            scanf("%s", str);
            int len = 0;
            while (str[len])
                ++len;
            ac::ins(str, len);
        }
        ac::build();
        for (i = 0; i < sz; ++i)
        {
            for (j = 0; j < n; ++j)
            {
                int v = L[i].nxt[j];
                if (L[v].flag)
                    continue;
                G[i][v] = 1;
            }
        }
        dp[0][0] = 1;
        for (i = 0; i < m; ++i)
        {
            for (j = 0; j < sz; ++j)
            {
                for (k = 0; k < n; ++k)
                {
                    int v = L[j].nxt[k];
                    if (G[j][v])
                        dp[i + 1][v] += dp[i][j];
                }
            }
        }
        bign ans = 0;
        for (i = 0; i < sz; ++i)
            ans += dp[m][i];
        cout << ans << endl;
    }
    return 0;
}