ABC242E解题报告

Empty_Dream · 2024-01-20 14:33:11 · 题解

题意

有 t 组数据，每组一个长度为 n 的字符串 s。求有多少个长度为 n 的回文串 x，使得 x \le s，对 998244353 取模。

分析

参考 C题 的思路，还是类似递推的做法。

对于两个字符串 s 和 t，只要 t 前面有一个字符小于 s 的对应字符，那么后面的所有字符无论多大肯定是小于 s 的，而后面的字符无论是什么都不影响，可以直接乘上 26。

根据这个性质，定义 dp_i 表示到第 i 个字符时回文串的方案数，我们可以得到转移方程 dp_i=dp_{i-1} \times26+a_i，其中 a_i 表示 s_i 减去 A 的值（即可以取多少个小于 s_i 的字符）。但是有个 bug，这个代码只能处理每一个字符都小于 s_i 的情况，而无法判断全部等于 s 时的情况，需要一个 check 去判断前半段字符都与 s 相等时是否合法。最后答案就是 dp_n+check。

最后加上 check 后一定要再模 998244353。

在每一次询问时一定不要清空 dp 数组，不然会 TLE！！！警钟敲烂。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int mod = 998244353;
int t, n;
int dp[1000005];
string s;

bool check(){//判断原串是否能是回文
    string t = " ";
    for (int i = 1; i <= (n + 1) / 2; i++) t += s[i];
    for (int i = n - (n + 1) / 2; i >= 1; i--) t += s[i];
    return t <= s;
}

signed main(){
    cin >> t;
    while (t--){
        cin >> n >> s;
        s = ' ' + s;
        for (int i = 1; i <= (n + 1) / 2; i++) dp[i] = (dp[i - 1] * 26 + s[i] - 'A') % mod;//递推
        cout << (dp[(n + 1) / 2] + check()) % mod << endl;
    }
    return 0;
}