Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Marcin Knapik
- #pragma GCC optimize("O3")
- #include <bits/stdc++.h>
- using namespace std;
- #define sz(x) ((int)(x).size())
- #define pb push_back
- #define all(s) s.begin(), s.end()
- #define f first
- #define s second
- const int N = 1e6 + 6;
- const int mod = 998244353;
- #define vi vector<int>
- #define vvi vector<vi>
- int f(int a, int b, int c){
- return a * 40 + b * 8 + (a == b ? 0 : c);
- }
- vvi operator * (vvi & a, vvi & b){
- int n = sz(a);
- assert(sz(a) and sz(b));
- assert(sz(a) == sz(a[0]) and sz(a[0]) == sz(b) and sz(b) == sz(b[0]));
- vvi ret(n, vi(n, 0));
- for(int i = 0; i < n; i++)
- for(int j = 0; j < n; j++)
- for(int k = 0; k < n; k++)
- ret[i][j] = (ret[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
- return ret;
- }
- vvi fast(vvi a, int b){
- vvi ret = a;
- for(int i = 0; i < sz(ret); i++)
- for(int j = 0; j < sz(ret); j++)
- ret[i][j] = (i == j);
- while(b){
- if(b & 1)
- ret = ret * a;
- a = a * a;
- b /= 2;
- }
- return ret;
- }
- void solve(){
- int n, m;
- cin >> n >> m;
- vector<string> tab(n);
- for(int i = 0; i < n; i++)
- cin >> tab[i];
- vvi row(5 * 5 * 8, vi(5 * 5 * 8));
- row[0][f(0, 0, 0)] = 1;
- vvi mat(5 * 5 * 8, vi(5 * 5 * 8));
- for(int i = 1; i <= 4; i++)
- for(int j = 1; j <= 4; j++)
- for(int k = 0; k < n; k++)
- mat[f(i, j, k)][f(i - 1, j - 1, k)] = 1;
- for(int i = 0; i <= 4; i++)
- for(int j = 0; j <= 4; j++)
- for(int k = 0; k < n; k++){
- if(i == 0 and j == 0 and k == 0)
- for(int a = 0; a < n; a++)
- for(int b = 0; b < n; b++){
- int dl = min(sz(tab[a]), sz(tab[b]));
- if(tab[a].substr(0, dl) == tab[b].substr(0, dl))
- mat[f(0, 0, 0)][f(sz(tab[a]) - 1, sz(tab[b]) - 1,
- (sz(tab[a]) > sz(tab[b]) ? a : b))] += 1;
- }
- else if(i != j and min(i, j) == 0)
- for(int a = 0; a < n; a++){
- int dl = min(abs(i - j), sz(tab[a]));
- if(sz(tab[k]) - abs(i - j) < 0)
- continue;
- if(tab[a].substr(0, dl) ==
- tab[k].substr(sz(tab[k]) - abs(i - j), dl))
- mat[f(i, j, k)]
- [f(i - 1 + (i < j) * sz(tab[a]), j - 1 + (j < i) * sz(tab[a]),
- (abs(i - j) > dl ? k : a))] += 1;
- }
- }
- vvi pot = fast(mat, m);
- vvi ret = row * pot;
- cout << ret[0][f(0, 0, 0)] << '\n';
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int tt = 1;
- // cin >> tt;
- for(int i = 0; i < tt; i++)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement