2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) E.Passwords AC自动机+dp

题目链接：点这里

题意：

　　让你构造一个长度范围在[A,B]之间 字符串(大小写字母，数字)，问你有多少种方案

　　需要满足条件一下：

　　　　1:构成串中至少包含一个数字，一个大写字母，一个小写字母；

　　  　 2:不能包含给定的N个病毒串

3:遵循一堆映射规则

题解：

　　将病毒串建立AC自动机

　　设定dp[i][j] [0/1][0/1][0/1]：表示构造长度为i，在自动机上面的状态是j，分别是否含有数字，大写字母，小写字母的情况

　　你能转移的点就是 加上一个数字或者大小写字母，暴力转移DP就好了，方程复杂度：20*1000*8，转移复杂度：26+26+10

　　整体复杂度：20*1000*8*62+建立trie

#include<bits/stdc++.h>

using namespace std;

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 1e6+, M = 1e3+;

LL mod = ;

int nex[][],q[],fail[],cnt=,black[],head,tail;

int rea_ID(int ch) {

    if(ch >=  && ch < ) return ch;

    if(ch == ) return 'o'-'a';

    if(ch == ) return 'i'-'a';

    if(ch == ) return 'e'-'a';

    if(ch == ) return 's'-'a';

    if(ch == ) return 't'-'a';

    if(ch >=  && ch <= ) return ;

    if(ch >  && ch <= )return ch - ;

}

int ID(char ch) {

    return ch - 'a';

}

void insert(char *s) {

    int now = , len = strlen(s);

    for(int i = ; i < len; ++i) {

        int index = ID(s[i]);

        if(!nex[now][index])

            nex[now][index] = ++cnt;

        now = nex[now][index];

    }

    black[now] |= ;

}

void build_fail() {

    head = , tail = ;

    for(int i = ; i < ; ++i) nex[][i] = ;

    fail[] = ;

    q[tail++] = ;

    while(head != tail) {

        int now = q[head++];

        black[now] |= black[fail[now]];

        for(int i = ; i < ; ++i) {

            int p = fail[now];

            if(!nex[now][i]) {

                nex[now][i] = nex[p][i];continue;

            }

            fail[nex[now][i]] = nex[p][i];

            q[tail++] = nex[now][i];

        }

        nex[now][] = ;

    }

}

int A,B,n;

char s[];

LL dp[][][][][];

int main()

{

    scanf("%d%d",&A,&B);

    scanf("%d",&n);

    for(int i = ; i <= n; ++i) {

        scanf("%s",s);

        insert(s);

    }

    build_fail();

    dp[][][][][] = ;

    for(int i = ; i <= B; ++i) {

        for(int j = ; j <= cnt; ++j) {

            for(int dxziok = ; dxziok <= ; ++dxziok)

            for(int shuziok = ; shuziok <= ; ++shuziok)

            for(int xxziok = ; xxziok <= ; ++xxziok) {

                if(dp[i][j][dxziok][shuziok][xxziok] == ) continue;

                for(int k = ; k <= ; ++k) {

                    int rea = rea_ID(k);

                    int tmp1 = ,tmp2 = ,tmp3 = ;

                    if(k < ) tmp1 = ;

                    else if(k <= ) tmp2 = ;

                    else tmp3 = ;

                    if(!black[nex[j][rea]])

                        dp[i+][nex[j][rea]][dxziok|tmp1][shuziok|tmp2][xxziok|tmp3] +=

                        dp[i][j][dxziok][shuziok][xxziok];

                        dp[i+][nex[j][rea]][dxziok|tmp1][shuziok|tmp2][xxziok|tmp3]%=mod;

                }

            }

        }

    }

    LL ans = ;

    for(int i = A; i <= B; ++i) {

        for(int j = ; j <= cnt; ++j) {

                ans = (ans + dp[i][j][][][])%mod;

            }

        }

    cout<<ans<<endl;

    return ;

}