Submission #68645041

---

Source Code Expand

#include<bits/stdc++.h>
namespace rgs = std::ranges;
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int N = 100005;
const int mod = 998244353;
const int sig = 26;
int son[N][sig], fail[N], cnt;
int p[N];
int ins(const char * c) {
	int x = 0;
	for(;*c;++c) {
		int & p = son[x][*c - 'a'];
		if(!p) p = ++ cnt;
		x = p;
	}
	return x;
}
void build_ac() {
	std::queue<int> Q;
	for(int i = 0;i < sig;++i) if(son[0][i]) Q.push(son[0][i]);
	for(;Q.size();) {
		int x = Q.front(); Q.pop();
		p[x] |= p[fail[x]];
		for(int i = 0;i < sig;++i)
			if(son[x][i]) fail[son[x][i]] = son[fail[x]][i], Q.push(son[x][i]);
			else son[x][i] = son[fail[x]][i];
	}
}
int dp[1005][100][1 << 8];
void add(int & x, int y) {
	if((x += y) >= mod) {
		x -= mod;
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	int n, l;
	cin >> n >> l;
	for(int i = 0;i < n;++i) {
		std::string s;
		cin >> s;
		int id = ins(s.c_str());
		p[id] |= 1 << i;
	}
	build_ac();
	dp[0][0][0] = 1;
	for(int i = 0;i < l;++i) {
		for(int j = 0;j <= cnt;++j) {
			for(int k = 0;k < 1 << n;++k) {
				for(int l = 0;l < 26;++l) {
					add(dp[i + 1][son[j][l]][k | p[son[j][l]]], dp[i][j][k]);
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0;i <= cnt;++i) {
		add(ans, dp[l][i][(1 << n) - 1]);
	}
	cout << ans << '\n';
}

Submission Info

Judge Result