分析

要求多少种串，要求规定的串不能出现。这个我们先对所有不能到的串建一个 自动机。那么我们可以根据 指针指向最长后缀这个性质来更新，是否能出现这个串的标记。令 表示 节点表示的串能否出现，那么转移方式，简单的来说就是 。那么我们定义 为 结尾的串的方案数。那么我们的转移为 而且 都没有 标记。那么这个朴素的转移为 由于 很大， 又很小。所以我们考虑矩阵优化转移，那么总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 100,mod = 1e9 + 7;
int ch[N][26],vis[N],fail[N],n,m,size;
char S[N];
struct matrix {
    int s[210][210];
    void clear() {memset(s,0,sizeof(s));}
    matrix operator *(const matrix x) const {
        matrix z;z.clear();
        for(int i = 0;i <= size;i++) {
            for(int j = 0;j <= size;j++) {
                for(int k = 0;k <= size;k++) {
                    z.s[i][j] = (z.s[i][j] + (1LL * s[i][k] * x.s[k][j] % mod)) % mod;
                }
            }
        }
        return z;
    }
}ans,base;
int main() {
    scanf("%d%d",&n,&m);
    while(m--) {
        int len,u = 0;scanf("%d%s",&len,S+1);
        for(int i = 1;i <= len;i++) {
            int c = S[i] - 'a';
            if(!ch[u][c]) ch[u][c] = ++size;
            u = ch[u][c];
        }vis[u] |= 1;
    }
    queue<int> Q;for(int i = 0;i < 26;i++) if(ch[0][i]) Q.push(ch[0][i]);
    while(!Q.empty()) {
        int u = Q.front();Q.pop();for(int i = 0;i < 26;i++) {
            int v = ch[u][i];if(v) {
                fail[v] = ch[fail[u]][i];vis[v] |= vis[fail[v]];Q.push(v);
            }
            else ch[u][i] = ch[fail[u]][i];
        }
    }
    ans.clear();base.clear();
    for(int i = 0;i <= size;i++) ans.s[i][i] = 1;
    for(int i = 0;i <= size;i++) {
        for(int j = 0;j < 26;j++) {
            if(vis[i] || vis[ch[i][j]]) continue;
            base.s[i][ch[i][j]] += 1;
        }
    }
    for(;n;n>>=1,base = base * base) if(n&1) ans = ans * base;
    for(int i = 1;i <= size;i++) ans.s[0][i] = (ans.s[0][i] + ans.s[0][i-1]) % mod;
    cout << ans.s[0][size] << endl;
    return 0;
}