HDU 6086 Rikka with String(AC 자동기+상압 dp, 2017 Multi-Univ Training Contest 5)

Problem

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has n 01 strings si, and he wants to know the number of 01 antisymmetric strings of length 2L which contain all given strings si as continuous substrings.
A 01 string s is antisymmetric if and only if s[i]≠s[|s|−i+1] for all i∈[1,|s|].
It is too difficult for Rikka. Can you help her?
In the second sample, the strings which satisfy all the restrictions are 000111,001011,011001,100110.
주어진 n개의 01열 si에 대해 2L의 반회문 문자열 (antisymmeric strings) 을 구하여 n개의 문자열이 모두 하위 문자열로 나타났다.
그 중에서 반회문 직렬 s가si≠s|s||-3i+1을 만족시킨다

Limit

1≤n≤6
1≤L≤100
1≤∣si∣≤20

Idea

만약 반환문열의 문제를 고려하지 않는다면, 이 문제는 간단한 AC자동기 + dp (물론 상압이 필요하다) 의 문제이다.이해할 수 없으면 직접 검색하십시오.
반회문의 설정이 있기 때문에 2L 길이의 01열에 대해 현재 L 길이가 알려졌을 때 이후 L 길이는 반드시 확정된다.그러므로 세 가지 상황을 고려하면 문자열 si는 앞 L에 있고 뒤 L 또는 일부는 앞 L 부분에서 뒤 L에 있다.

문자열 si가 앞 L에 떨어진 문제는 AC 자동기에 원래 문자열si를 직접 삽입합니다.

문자열 si가 뒤 L에 떨어지는 문제. 이 문자열은 앞의 L에서 그 자체의 역역역렬(즉reverse(s i)이 한 사람당 01을 반올림)을 AC자동기에 원렬의 역렬을 삽입하는 것을 나타낸다.

문자열 si 부분이 앞의 L 부분에서 뒤의 L에 있는 문제는 앞의 L 길이와 뒤의 L 길이를 구분해야 하기 때문에 반회문 문자열의 제한을 충족시키지 못하는 부분이 있다.그러므로 여러 가지 고려를 필요로 한다.한 마디로 하면 매거의 합법적인 가능성에 대해 구조는 이 직렬을 이 전후 L 결합 부분의 직렬ss(구체적jugGapAndInsert() 함수)에 완전하게 나타나게 하고 이를 AC자동기에 가입시킬 수 있다.

AC 자동기는 fail 포인터를 생성한 후 dp를 직접 상압한다.

Code

#include
using namespace std;
char s[6][22], ss[22];
const int maxn = 1000+10;
const int mod = 998244353;
const int CH = 3;
int t, n, L, dp[101][maxn][128];
struct Trie {
    int nxt[maxn][CH], fail[maxn], end[maxn], isEnd[maxn];
    int root, L;
    void init() {
        L = 0;
        root = newnode();
    }
    int newnode() {
        for(int i=0;i1;
        isEnd[L] = 0;
        end[L++] = 0;
        return L-1;
    }
    void insert(char buf[], int len, int idx, bool flg) {
        int p = root;
        for(int i=0;iif(nxt[p][buf[i]] == -1)
                nxt[p][buf[i]] = newnode();
            p = nxt[p][buf[i]];
        }   
        if(flg) isEnd[p] |= (1<else    end[p] |= (1<1<void build() {
        queue<int> que;
        fail[root] = root;
        for(int i=0;iif(nxt[root][i] == -1)
                nxt[root][i] = root;
            else
                fail[nxt[root][i]] = root,
                que.push(nxt[root][i]);
        while(!que.empty()) {
            int p = que.front();
            que.pop();
            for(int i=0;iif(nxt[p][i] == -1)
                    nxt[p][i] = nxt[fail[p]][i];
                else {
                    fail[nxt[p][i]] = nxt[fail[p]][i];
                    que.push(nxt[p][i]);
                }
        }
    }

    void debug(){
        for(int i = 0;i < L;i++) {
            printf("id = %2d,fail = %3d,end = %3d, isEnd = %d, chi = [",i,fail[i],end[i],isEnd[i]);
            for(int j = 0;j < CH;j++)
                printf("%3d",nxt[i][j]);
            printf("]
");
        }
    }
}ac;
void jugGapAndInsert(int idx, int gap) {
    for(int i=0;;i++) {
        if(gap+i+1 == strlen(s[idx]) || gap-i < 0)  break;
        if(s[idx][gap+i+1] == s[idx][gap-i])    return;
    }   
    int len = strlen(s[idx]);
    if(gap+1 > len-gap-1) {
        ac.insert(s[idx], gap+1, idx, true);
    } else {
        for(int i=0;i1;i++)
            ss[i] = 3 - s[idx][len-i-1];
        ac.insert(ss, len-gap-1, idx, true);
    }
}
int main()
{
    scanf("%d", &t);
    while(t-- && scanf("%d %d", &n, &L)!=EOF)
    {
        ac.init();
        memset(dp, 0, sizeof(dp));
        for(int i=0, len;iscanf(" %s", s[i]);
            len = strlen(s[i]);
            for(int j=0;j'0' + 1;
                ss[len-j-1] = 3 - s[i][j];
            }
            ac.insert(s[i], len, i, false);
            ac.insert(ss, len, i, false);
            for(int j=0;j1;j++)
                jugGapAndInsert(i, j);
        }
        ac.build();
        //ac.debug();

        dp[0][0][0] = 1;
        for(int i=0, nxt, tmpNxt, status, isEnd;ifor(int j=0;jfor(int c=1;c<=2;c++)
        {   
            nxt = j;
            status = 0, isEnd = 0;
            nxt = ac.nxt[nxt][c];
            tmpNxt = nxt;
            while(tmpNxt != 0) {
                status |= ac.end[tmpNxt];
                if(i+1==L)  status |= ac.isEnd[tmpNxt];
                tmpNxt = ac.fail[tmpNxt];
            }

            for(int S=0;S1<1][nxt][S|status] += dp[i][j][S]) %= mod;
        }
        long long ans = 0;
        for(int j=0;j1<1]) %= mod;
        printf("%lld
", ans);
    }
}