「TPOI-1C」Standard Problem. Solution

sunkuangzheng · 2025-02-14 18:25:42 · 题解

观察：在 s^k 中任意一个长度大于等于 n 的回文串都可以向两侧无限延伸。

证明：设 s_{1\sim n} 是回文串，记 t = s^k，此时应有 t_0 = t_n = s_n,t_{n+1} = t_1 = s_1。因此 t[0,n+1] 也是回文串，以此类推即可。

考虑对 s+s+s 求出每个中心的回文半径，如果回文半径大于等于 \lceil \frac{n}{2} \rceil，那么这个回文串就可以无限延伸，贡献容易计算；否则这个回文中心在所有位置的贡献都是一样的（特判边界情况），贡献也不难计算。

时间复杂度线性。

/**
 *    author: sunkuangzheng
 *    created: 01.09.2024 16:17:57
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5,mod = 998244353;
using namespace std;
int T,n,m; string s;
vector<int> manachar(string t){
    string s; s = ".#";
    for(char c : t) s += c,s += '#';
    int n = s.size(),r = 0,mid = 0; vector<int> p(n);
    for(int i = 1;i < n;i ++){
        if(i <= r) p[i] = min(r - i + 1,p[2 * mid - i]);
        while(s[i - p[i]] == s[i + p[i]]) p[i] ++;
        if(i + p[i] - 1 > r) r = i + p[i] - 1,mid = i; 
    }for(int &i : p) i = i / 2;
    return p;
}void los(){
    cin >> n >> m >> s; ll ans = 0;
    auto p = manachar(s + s + s); s = " " + s;
    p.erase(p.begin()); 
    for(int k = 2 * n;;k ++){
        int i = (k + 1) / 2 - n,j = k / 2 + 1 - n;
        if(j > n) break;
        if(p[k] >= n + (i == j)){
            int l = m / 2;
            ans = (ans + 1ll * l * (l - 1) % mod * n % mod + 1ll * (i + n - j + 1) * l) % mod;
            if(m & 1) ans = (ans + min(i,n - j + 1) + 1ll * l * n) % mod; 
        }else ans = (ans + 1ll * p[k] * (m - 2) + min(i,p[k]) + min(n - j + 1,p[k])) % mod; 
    }cout << ans << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}