String and LIS ICPC

#include     <bits/stdc++.h>
#ifndef      CONVICTION
#define      debug(x...)
#endif
#define IOS  ios_base::sync_with_stdio(false); cin.tie (nullptr)
#define PREC cout.precision (10); cout << fixed
#define F    first
#define S    second
#define int  long long
#define ff   long double
using namespace std;
//Don’t practice until you get it right. Practice until you can’t get it wrong

void preproc() { }

int n, q;
int prevdp[26][26], nextdp[26][26], seen[26], state[26][26];
const int D = 52;

// reference : https://codeforces.com/blog/entry/80195
struct Matrix {
   int a[D][D];
   Matrix() {
      for (int i = 0; i < D; ++i)
         for (int j = 0; j < D; ++j)
            a[i][j] = -1;
   }

   Matrix operator *(Matrix other) {
      Matrix res = Matrix();
      for (int i = 0; i < D; ++i)
         for (int j = 0; j < D; ++j)
            for (int k = 0; k < D; ++k)
               if ( a[i][j] != -1 and other.a[j][k] != -1 )
                  res.a[i][k] = max(res.a[i][k], a[i][j] + other.a[j][k]);

      return res;
   }
};

Matrix expo_power(Matrix a, int k) {
   Matrix res = Matrix();
   for (int i = 0; i < D; ++i)
      res.a[i][i] = 1;
   while(k) {
      if(k % 2)
         res = res * a;
      a = a * a;
      k /= 2;
   }
   return res;
}

void solve()
{
   cin >> n >> q;

   memset(state, -1, sizeof(state));

   string s;
   for (int i = 0; i < n; ++i) {
      cin >> s;
      memset(prevdp, -1, sizeof(prevdp));
      memset(nextdp, -1, sizeof(nextdp));
      memset(seen, 0, sizeof(seen));

      prevdp[s[0] - 'a'][s[0] - 'a'] = 1;

      for (int j = 1; j < (int)s.size(); ++j) {
         int fx = s[j]-'a';

         nextdp[fx][fx] = 1;
         for (int start = 0; start <= fx; ++start)  // 26
            for (int y = 0; y <= fx; ++y)
               if ( prevdp[start][y] != -1 )
                  nextdp[start][fx] = max(prevdp[start][fx], prevdp[start][y] + 1);

         for (int x = 0; x < 26; ++x)
            for (int y = 0; y < 26; ++y)
               prevdp[x][y] = nextdp[x][y];
      }

      for (int x = 0; x < 26; ++x)
         for (int y = x; y < 26; ++y)
            state[x][y] = max(state[x][y], prevdp[x][y]);
   }

   Matrix init = Matrix();
   for (int x = 0; x < 26; ++x)
      for (int y = x; y < 26; ++y)
         init.a[2*x][2*y] = state[x][y];


   for (int x = 0; x < 26; ++x) {
      init.a[2*x][2*x+1] = 0; // v-> v'
      init.a[2*x + 1][2*x + 1] = 0; // self loop v' <-> v'
   }

   Matrix res = expo_power(init, q+1);
   int ans = 0;
   for (int x = 0; x < 26; ++x)
      for (int y = x; y < 26; ++y)
         ans = max({ans, res.a[2*x][2*y + 1]});

   cout << ans << '\n';
}

signed main()
{
   IOS; PREC;
   preproc();

   int tc = 1;
   cin >> tc;
   for (int Tt = 1; Tt <= tc; ++Tt) {
      // cout << "Case #" << Tt << ": ";
      solve();
   }
   return EXIT_SUCCESS;
}