can it be done with dfs? i tried dfs but got wa on 11 cases.

Suppose we have an empty string and append a character to it $$$n$$$ times. After appending each character, we must ensure that the current string does not contain any restricted substrings. Suppose $$$s_i$$$ is the string after appending $$$i$$$ characters. Suppose after the $$$i-$$$th step, we appended character $$$c$$$ to string $$$s_i$$$ such that it becomes $$$s_{i+1}$$$. Now we should ensure that $$$s_{i+1}$$$ does not contain any of the banned substrings. Since $$$s_i$$$ is valid till now, we need to look at only the last $$$6$$$ characters of $$$s_{i+1}$$$ to check whether it is valid.

So we can look at it as a graph with an edge from $$$s_i$$$ to $$$s_{i+1}$$$. So we start our path from $$$s_0$$$(empty string) and reach $$$s_n$$$. Now we can have many possibilities for $$$s_i$$$, so we cannot store all $$$s_i$$$. Instead, we can just store the last $$$6$$$ characters of $$$s_i$$$.

So, to sum up, you can make a graph of $$$x$$$ nodes, where each node represents some string which does not contain any banned substring. One node will correspond to an empty string. So you can visualise string $$$s$$$ as movement(starting from an empty string) from one node to another via directed edge.

Since we are only concerned about strings of length less than $$$7$$$, $$$x \leq 127$$$.

Our answer is a number of walks starting from an empty node with length $$$n$$$, which can be easily done using matrix exponentiation.

Assume $$$s=abababab$$$ In this case,

• $$$s_0=$$$""
• $$$s_1=a$$$
• $$$s_2=ab$$$
• $$$s_3=aba$$$
• $$$s_4=abab$$$
• $$$s_5=ababa$$$
• $$$s_6=ababab$$$
• $$$s_7=bababa$$$(notice that actually $$$s_7=abababa$$$, but we are only concerned with last $$$6$$$ characters)
• $$$s_8=ababab$$$(notice that actually $$$s_8=abababab$$$, but we are only concerned with last $$$6$$$ characters)

queue<string> track;
    ll now=1;
    string use;
    track.push(use);
    pos[use]=1;   
    auto bad=[&](string check){
        for(auto it:avoid){
            ll l=it.size(),r=check.size();
            for(ll i=0;i<r;i++){
                if(i+l>n){
                    break;
                }
                if(check.substr(i,l)==it){  
                    return 1; 
                }
            }
        }
        return 0;
    };
    vector<ll> adj[MAX];
    while(!track.empty()){  
        use=track.front();
        track.pop();
        for(auto c:{'a','b'}){
            string cur=use; 
            cur.push_back(c);
            if(bad(cur)){
                continue;
            }
            if(cur.size()>6){
                cur.erase(cur.begin());
            }
            if(pos[cur]==0){
                pos[cur]=++now;
                track.push(cur);
            }
            ll l=pos[use],r=pos[cur];  
            adj[l].push_back(r);
        }
    }

Link to submission

Here is the $$$O(N . M . 2^6)$$$ dp

const int bit = 6;

vector<Mint> dp(1 << bit);

for(int mask = 0;mask < (1 << bit);mask++){
	if(ok(bit,mask)){
		dp[mask]++;
	}
}

for(int i = 0; i < n - bit; i++){
	vector<Mint> new_dp(1 << bit);
	for(int mask = 0;mask < (1 << bit);mask++){
		for(int k = 0; k < 2; k++){
			int new_mask = ((mask << 1) + k) & ((1 << bit) - 1);
			
			if(ok(bit,new_mask)){
				new_dp[new_mask] += dp[mask];
			}
		}
	}
	dp = new_dp;
}

Where the function ok(size,mask) just checks whether a banned substring occurs in the string mask. Now make the transition matrix from dp to new_dp.

matrix<Mint> mat(1 << bit,1 << bit);
for(int mask = 0;mask < (1 << bit);mask++){
	for(int k = 0; k < 2; k++){
		int nmask = ((mask << 1) + k) & ((1 << bit) - 1);
		if(ok(bit,nmask)){
			mat[mask][nmask] = 1;
		}
	}
}

Notice that new_dp = mat * dp. Your final answer is now power(mat,(n-bit)) * dp. You can calculate final dp in $$$O(\log n)$$$ instead of $$$O(n)$$$ using binary exponentiation. Here is my submission https://atcoder.jp/contests/abc305/submissions/42175122.

Consider Aho Corasick Automaton, where each node represent a state, and the edges are transitions. Inserting a string s will set all the states with the s as suffix bad. This can be precalculate by building the failure links. The problem can now be rephrased as "Starting from the root state, how many walks are there such that we didn't pass through a bad state", which can be done using matrix exponentiation.

Submission

You must check if the node is already in the (priority) queue before you push to it. If you don't do this, the time complexity may degenerate to (something higher than $$$O(V+E)$$$ but I am too lazy to prove a bound) in some cases. Learnt this through moments of pain. Many times it works without this optimization, but it is very important to know this.

I think u might have done the same mistake as I did. Once u output pre, u should read in the k vertices again, otherwise the input read later would be wrong.