Description

图片说明
简单的说就是定义一个回文串为 阶回文需要满足把他切成两半（, ，奇数长度中间的字符不用管）
然后这两半都是 阶的，定义回文串都可以是 阶。

Solution

不会双模数哈希，抄的题解，单模数一直被卡。
按照定义，显然是可以类似于 的思想去做的，定义所有朴素的回文串都为 阶，那么先找出所有的回文串，显然当前回文串 的阶数为左边的阶数，因此直接 统计所有答案即可。
由于有结论：本质不同回文串的数量级别为 ，所以通过 可以找到所有本质不同回文串并实现上述的赋值操作。需要用双模数哈希来判断是否本质不同，总体时间复杂度 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod1 = 998244353, mod2 = 1e9 + 9;
const int N = 5e5 + 5;
map<ll, int> mp;
int cal[N], p[N];
char s[N], str[N];
ll f1[N], f2[N], hs1[N], hs2[N];
void iniths(int n, ll hs[N], int b, int mod)
{
  for (int i = 1; i <= n; i++) {
    hs[i] = (hs[i - 1] * b % mod + s[i] - 'a' + 1) % mod;
  }
}
int geths(int l, int r, ll hs[N], ll f[N], int mod)
{
  return (hs[r] - hs[l - 1] * f[r - l + 1] % mod + mod) % mod;
}
ll __hash(int l, int r)
{
  return geths(l, r, hs1, f1, mod1) * 123456ll + geths(l, r, hs2, f2, mod2);
}
void update(int l, int r) {
  if (l == r) {
    mp[__hash(l, r)] = 1;
  } else {
    mp[__hash(l, r)] = mp[__hash(l, (l + r - 1) / 2)] + 1;
  }
}
void manacher(int n) {
  str[1] = '$';
  for (int i = 1; i <= n; i++) {
    str[i << 1] = s[i], str[i << 1 | 1] = '#';
  }
  str[(n + 1) << 1] = '*';
  int id = 0, mx = 0;
  for (int i = 1; i <= 2 * n + 1; i++) {
    if (i <= mx) {
      p[i] = min(mx - i, p[2 * id - i]);
    } else {
      p[i] = 1;
    }
    while (str[i + p[i]] == str[i - p[i]]) {
      p[i]++;
      int len = (p[i] + (i % 2 == 0)) / 2 - 1;
      if (len >= 0) {
        if (i & 1) {
          update(i / 2 - len, (i + 1) / 2 + len);
        } else {
          update(i / 2 - len, i / 2 + len);
        }
      }
    }
    if (i + p[i] > mx) {
      mx = i + p[i], id = i;
    }
  }
}
void solve() {
  int n, m; cin >> n >> m;
  cin >> (s + 1);
  mp.clear();
  for (int i = 0; i <= n; i++) {
    cal[i] = 0;
  }
  iniths(n, hs1, 233, mod1);
  iniths(n, hs2, 31, mod2);
  manacher(n);
  for (auto &it : mp) {
    cal[it.second]++;
  }
  for (int i = n - 1; i >= 0; i--) {
    cal[i] += cal[i + 1];
    cal[i] %= mod1;
  }
  ll ans = 0;
  int res = 2;
  for (int i = 1; i <= m; i++) {
    ans += 1LL * res * cal[i] % mod1;
    ans %= mod1;
    res = res * 2LL % mod1;
  }
  cout << ans << '\n';
}
void prework() {
  f1[0] = f2[0] = 1;
  for (int i = 1; i <= N - 1; i++) {
    f1[i] = f1[i - 1] * 233 % mod1;
    f2[i] = f2[i - 1] * 31 % mod2;
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int T = 1; cin >> T;
  prework();
  while (T--) {
    solve();
  }
  return 0;
}
/*
10
0 1 0 0 0 1 0 0 0 1
*/