显而易见的，回文串最多只有一个字符出现次数是奇数。 奇偶性我们可以简单地用 0/10/10/1 代替。所以，我们有 262626 个字母，每个字母有 0/10/10/1 两种状态。所以我们可以使用状态压缩！（题目1024MB也是一种提醒） 所以，dpmaskdp_{mask}dpmask 表示当目前前缀状态为 maskmaskmask 的时候的合法子串数量（目前，是指目前处理到了哪一位）。 首先记录一下目前的前缀 ppp，然后将答案加上 dppdp_pdpp 。 同时，我们知道，有可能会有一个字母出现奇数次。枚举这个字母，并记录答案。 最后，记得用 ppp 更新 dppdp_pdpp 的值。 注意下，一开始 dp0=1dp_0=1dp0 =1，因为任何字母都出现 000 次。 时间复杂度：O(n)O(n)O(n) 空间复杂度：O(n+226)O(n+2^{26})O(n+226) Code:

T6 午枫的字符串制造 题目大意 给定一个长度为 nnn 的字符串，求有多少个连续子串可以通过重新排列得到回文串。 题解思路 首先，如果用 O(n2)O(n^2)O(n2) 暴力枚举所有区间肯定是不可行的。于是我们需要考虑优化。 我们如何可以快速判断一个子串能否通过重新排列得到一个回文串？ 不难发现，如果这个子串的长度是偶数，那么所有的字母的个数都是偶数就可以排列成回文串；如果这个子串的长度是奇数，那么只能有一个字母的个数是奇数，才可以排列成回文串。 那么我们可以用长度为 262626 的二进制状态表示每一个字母个数的奇偶。 奇偶性可以通过异或来表达。记 StateiState_iStatei 为前 iii 个字母的奇偶状态，定义 State0=0State_0=0State0 =0 ，cntStatecnt_{State}cntState 为 StateStateState 这种状态的数量。我们可以通过枚举区间右端点 iii ，得到 StateiState_iStatei ，那么我们可以考虑分回文串的奇偶长度分两个情况考虑： * 回文串的长度为偶数，此时有 cntStatejcnt_{State_j}cntStatej 个左端点 jjj 可以形成回文串，其中 0≤j≤i−10\leq j\leq i-10≤j≤i−1 且 Statei=StatejState_i=State_jStatei =Statej 。 * 回文串的长度为奇数，此时我们可以枚举 262626 个字母为奇数状态的情况，设第 kkk 个字母的个数是奇数的状态为 mask=Statei⊕(1<<k)mask=State_i\oplus (1<<k)mask=Statei ⊕(1<<k) ，那么有 cntmaskcnt_{mask}cntmask 个左端点 jjj 可以形成回文串，其中 0≤j≤i−10\leq j\leq i-10≤j≤i−1 且 mask=Statejmask=State_jmask=Statej 。 字符串的长度为 nnn 且每个状态最多延申出 262626 个状态，空间复杂度最大为 O(26n)O(26n)O(26n) ，此题空间限制给了 1GB1GB1GB ，因此是可以通过的。 时间复杂度为 O(26n)O(26n)O(26n) 。 参考代码

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s; cin >> n >> s; const int MASK_MAX = 1 << 26; vector<int> dp(MASK_MAX, 0); dp[0] = 1; int mask = 0; long long ans = 0; for (char c : s) { mask ^= (1 << (c - 'a')); ans += dp[mask]; int temp = mask; for (int j = 0; j < 26; j) { temp ^= (1 << j); ans += dp[temp]; temp ^= (1 << j); } dp[mask]; } cout << ans << '\n'; return 0; }