中心拓展法求回文

牛客134 F

题目大意：

给一个字符串，求的是这个字符串的的总价值，这个总价值的求法是，这个字符串中所有回文连续子字符串的价值总和，这个回文子字符串的价值总和就是这个子字符串的长度的平方
（这位更是重量级：（https://anoth3r.top/nkwk134/））

code

#include<bits/stdc++.h>
using namespace std;
//"O campeão tem nome, e se chama Charles Oliveira!"
#define int long long
#define endl '\n'
#define emplace ep
#define pob 
#define ll long long
#define pb push_back
#define pof pop_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define mod 998244353
#define MOD 1000000007using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;//求回文的中心拓展法
//牛客134 F
void solve() {int n;string s;cin >> n >> s;vector<vector<bool>> flag(n + 1, vector<bool>(n + 1));for (int i = 0; i < n; ++i) {int l = i, r = i;while (l >= 0 && r < n && s[l] == s[r]) {flag[l + 1][r + 1] = 1;l--, r++;}l = i, r = i + 1;while (l >= 0 && r < n && s[l] == s[r]) {flag[l + 1][r + 1] = 1;l--, r++;}}vector<int> dp1(n + 1), dp2(n + 1);//dp1是方案数字，dp2是总的价值数// dp1是前缀1到i的方案数的总和//dp2是前缀1到i的价值数的总和dp1[0] = 1, dp2[0] = 0;for (int i = 1; i <= n; ++i) {for (int j = 0; j < i; ++j) {if (flag[j + 1][i]) {dp1[i]=(dp1[i]+dp1[j])%mod;dp2[i]=(dp2[i]+dp2[j] + dp1[j] * (i - j) * (i - j))%mod;}}}cout << dp2[n]%mod << endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t=1;cin>>t;while(t--)solve();
}