dinnerhunt

Progressive hard octave rock tunes (so-called “phorts”) are written using a specifific music notation. This flflavor of rock is built on just 13 difffferent note pitches, other pitches (in other octaves)are considered to be an outdated musical ballast. Each note can be either a long one or a shortone. Consequently, there are exactly 26 difffferent notes in the rock.

You are going to compose a phort tune on the occasion of your friend’s birthday and perform itwith your band on the main town square. While composing the phort, you need to avoid certainmusical phrases, which are heavily copyrighted as a result of long research sponsored by bigrecord companies. It has been established that these phrases are very catchy, easy to remember,and could be exploited to bind the listeners subconsciously to a particular music company whichwould utilize these phrases in their production.

The tune is a sequence of notes. A musical phrase is also a sequence of notes and it is consideredto be contained in a tune if its notes form a contiguous subsequence of the tune, which meansthe same notes appear in the tune right after each other in the same order.

Fortunately, only a few forbidden phrases have been patented so far. Thus, you have a relativefreedom in composing your own tunes. In particular, you are interested in the number ofacceptable tunes of some length. An acceptable tune is any tune which does not contain aforbidden phrase. The length of the tune is equal to the number of notes it contains.

大致题意 📖

给定$q$个长度和不超过100的字符串
求长度为$n$，不包含上面任意子串的字符串方案数

链接 🔗

「ICPC Central Europe Regional Contest 2019」 G. K==S

题解 ❓

将不合法字符串构建自动机，然后对于每个节点打算不合法标记
然后就将问题转化成了从点$1$开始，不能到达不合法点方案数
这样就变成了 TJOI2017 可乐
注意一下，对于一个点$x$,如果$fail[x]$不合法，那么$x$也不合法

代码

const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = acos(-1);
const int N = 2e5+10;
struct AC_Automaton
{
    ll ch[N][26],fail[N],cnt[N],tot;
    void init()
    {
        MM(ch,-1);MM(fail,0);MM(cnt,0);
        tot = 0;
    }
    void insert(char *s)
    {
        ll p = 0,len = strlen(s);
        FOR(i,0,len-1)
        {
            if(ch[p][s[i] - 'a'] == -1) ch[p][s[i]-'a'] = ++tot;
            p = ch[p][s[i] - 'a'];
        }
        cnt[p]++;
    }
    void build()
    {
        queue<ll> que;
        FOR(i,0,25)
        {
            if(ch[0][i] == -1) ch[0][i] = 0;
            else que.push(ch[0][i]);
        }
        while(!que.empty())
        {
            ll p = que.front(); que.pop();
            FOR(i,0,25)
            {
                if(ch[p][i] == -1) ch[p][i] = ch[fail[p]][i];
                else
                {
                    fail[ch[p][i]] = ch[fail[p]][i], que.push(ch[p][i]);
                    cnt[ch[p][i]] |= cnt[ch[fail[p]][i]];
                }
            }
        }
    }
}AC;
char s[201];
struct Matrix_Pow
{
    ll n;
    struct matrix
    {
        long long a[205][205];
    }ans,base,C;
    void init()
    {
        MM(ans.a,0);
        MM(base.a,0);
        FOR(i,1,204) ans.a[i][i] = 1;
    }
    matrix matrix_mul(matrix A, matrix B)
    {
        matrix C;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
            {
                C.a[i][j] = 0;
                for (int k = 1; k <= n; ++k) C.a[i][j] = (C.a[i][j] + (A.a[i][k] * B.a[k][j] % mod)) % mod;
            }
        return C;
    }
    void matrix_pow(long long b)
    {
        for (; b; b >>= 1)
        {
            if (b & 1) ans = matrix_mul(ans, base);
            base = matrix_mul(base, base);
        }
    }
}M;
int main()
{
//    __IN;__OUT;
    ll n,m;RLL2(n,m);
    AC.init();
    FOR(i,1,m)
    {
        ll x;RLL(x);
        RS(s);
        AC.insert(s);
    }
    AC.build();
    M.init();
    M.n = AC.tot+1;
    FOR(i,0,AC.tot)
    {
        if(AC.cnt[i]) continue;
        FOR(j,0,25)
        {
            ll v = AC.ch[i][j];
            if(AC.cnt[v]) continue;
            if(AC.ch[i][j] == -1) v = 0;
            M.base.a[i+1][v+1]++;
        }
    }
    M.matrix_pow(n);
    ll ans = 0;
    FOR(i,1,AC.tot+1)
        ans = (ans + M.ans.a[1][i])%mod;
    PLN(ans);
    return 0;
}