C++(clang++11) 解法, 执行用时: 11ms, 内存消耗: 1272K, 提交时间: 2021-05-14 19:32:08

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 5e5 + 100;
const int MOD = 998244353;

int n, m, tot;
int nex[N][26], fail[N], len[N], sa[N], dp[N], cnt[N];
char str[N];

void init() {
	for (int i = 0; i < tot; i++) {
		len[i] = fail[i] = 0;
		memset(nex[i], 0, sizeof(nex[i]));
	}
	fail[0] = 1; len[1] = -1; tot = 2;
}

int main() {
	//freopen("0.txt", "r", stdin);
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d%s", &n, &m, str + 1); init();
		for (int i = 1, p = 1; i <= n; i++) {
			int id = str[i] - 'a';
			while (str[i] != str[i - len[p] - 1]) p = fail[p];
			if (nex[p][id] == 0) {
				len[tot] = len[p] + 2;
				int v = fail[p];
				while (str[i] != str[i - len[v] - 1]) v = fail[v];
				fail[tot] = nex[v][id];
				nex[p][id] = tot++;
			}
			p = nex[p][id];
		}
		for (int i = 2; i < tot; i++) sa[i] = fail[i];
		for (int i = tot - 1; i > 1; i--) {
			if (len[i] == 1) continue;
			int p = fail[i];
			while (len[p] > len[i] / 2) p = fail[p];
			sa[i] = p;
			if (len[sa[fail[i]]] > len[sa[i]]) sa[fail[i]] = sa[i];
		}
		for (int i = 2; i < tot; i++) {
			if (len[i] == 1 || len[sa[i]] != len[i] / 2) dp[i] = 1;
			else dp[i] = dp[sa[i]] + 1;
			cnt[dp[i]]++;
		}
		for (int i = tot - 1; i >= 1; i--) cnt[i] += cnt[i + 1];
		ll ans = 0;
		for (int i = 1, j = 2; i <= m; i++, j = j * 2 % MOD) ans = (ans + 1LL * cnt[i] * j) % MOD;
		printf("%lld\n", ans);
		for (int i = 0; i <= tot + 5; i++) cnt[i] = 0;
	}
	return 0;
}