链接：https://ac.nowcoder.com/acm/problem/21587 来源：牛客网

题号：NC21587 时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒 空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M 64bit IO Format: %lld 题目描述 我们称正着读与反着读一样的串为回文串，比如abba与racecar都是回文串 我们称长度为奇数的回文为奇回文，中间的字符称为回文中心

有一个字符串S包含N个小写字母 令x[i]表示以i为回文中心的回文子序列的个数 (0 <= i <= N-1) 换句话说：保留第i个字符，X[i]表示有多少种字符的删除方案可以使得剩下的字符是一个以i为中心的回文串

Y[i] = ((i+1) * X[i])%1000000007 返回所有Y的xor之和

所有字母都是小写字母 输入描述: 输入一行包含一个字符串，字符串的长度（1 <= N <= 3000） 输出描述: 输出一个整数

方案1：

注意到：奇回文序列如果删掉回文中心，再把后半段字符串reverse一下，会得到两段一模一样的字符串，可以用这点统计回文中心对应回文子序列数量。例如字符串axbcba，要统计以第一个b为回文中心的回文子序列数，就把字符串按b分割成ax、cba两个字符串，再用reverse把cba倒转成abc，ax与abc的公共子序列数就是原字符串以b为回文中心，去掉b这种情况后的所有情况数，最后加上b这种情况，就得到了以b为回文中心的回文序列数。现在看所有情况，对axbcba和它的反转abcbax，求下标i为中心的回文序列数，等价于求axbcba的前i个字符组和abcbax前len(字符串长度)-i-2个字符的公共序列数+1，这样题目就变成了输入字符串s1，和s1的反转字符串s2，求s1，s2的公共子序列数加1后的值。

代码：

#include<string>
#include<vector>
#include<algorithm>

using ll = long long;
using namespace std;
const int MOD = 1e9 + 7;

ll DP(const string& s)
{
	int len = s.length();
	if (len == 0)return 0;
	vector<vector<ll>>dp(len + 1, vector<ll>(len + 1, 0));
	string s2(s);
	reverse(s2.begin(), s2.end());
	//cout << "s2: " << s2 << endl;
	for (int i = 1; i <= len; i++)
	{
		for (int j = 1; j <= len; j++)
		{
			if (s[i-1] == s2[j-1])
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1;
				dp[i][j] %= MOD;
			}
			else
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + MOD;
				dp[i][j] %= MOD;
			}
		}
	}
	vector<ll>ans(len, 0);
	ans[0] = 1;
	ans[len - 1] = 1;
	ll num = 0;
	for (int i = 1; i < len-1; i++)
	{
		ans[i] = dp[i][len - i - 1] + 1;
		ans[i] %= MOD;
	}
	//debug
	/*for (int i = 1; i <= len; i++)
	{
		for (int j = 1; j <= len; j++)
		{
			cout << "dp[" << i << "][" << j << "]:" << dp[i][j] << endl;
		}
	}*/
	for (int i = 0; i < len; i++)
	{
		num ^= (ans[i] * (i + 1))%MOD;
		//cout << "ans[" << i << "]:" << ans[i] << endl;
	}
	return num;
}
int main(void)
{
	string s;
	cin >> s;
	cout << DP(s);
	return 0;
}

方案2：

如果用贡献的思维看这题呢？cbabc中，a为回文中心的回文序列有4个，我们把这四个分成1+1+(1+1),最开始只有a，然后b出现配对了，就多了bab这种方案，之后c又配对了，多了cac这种方案，而且c可以与b联合贡献cbabc这种方案，即1+1+(1+1),每有一个字符配对，就会多出这个字符配对所贡献的方案数和这个字符与之前字符联合贡献的方案数，那岂不是要对每个回文中心算字符配对？dp呗，要上一轮的dp可以用于这一轮的联合贡献，所以字符串要从内到外或者从外到内，我们设置一个i作为回文中心，最开始只有i这一种方案，随后i的方案数加上配对贡献的方案数，每次从最右端往i-1的位置开始配对，然后最右端-1的位置与i-1尝试配对，每次配对成功后，i的方案数就累加1(新的单独配对)与新联合贡献数方案。(虽然最开始有这种思路，但是分层硬是分不出来，方案2是对大佬解法的解读)

代码:

#include<string>
#include<vector>

using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

ll DP(const string&s)
{
	int len = s.length();
	vector<vector<ll>>dp(len, vector<ll>(len, 0));//以下标i为回文中心，j为字符下标的方案数
	vector<ll>ans(len, 0);//记录每个回文中心回文序列数
	ans[0] = 1;
	ans[len - 1] = 1;
	for (int i = 1; i < len - 1; i++)
	{
		ans[i] = 1;//对应只有自身这种情况
		ll sum = 0;//记录i-1下标为回文中心时的方案总数，用于联合贡献
		for (int j = len - 1; j > i; j--)
		{
			dp[i][j] += dp[i - 1][j];
			dp[i][j] %= MOD;
			if (s[j] == s[i - 1])
			{
				dp[i][j] += sum + 1;//sum是联合贡献数，+1表示的是j与i-1，i组成的回文串
				dp[i][j] %= MOD;
			}
			sum += dp[i - 1][j];
			ans[i] += dp[i][j];
			ans[i] %= MOD;
		}
	}
	int num = 0;
	for (int i = 0; i < len; i++)
	{
		cout << "ans[" << i << "]: " << ans[i] << endl;
		num ^= (i + 1) * ans[i] % MOD;
	}
	return num;
}
int main(void)
{
	string s;
	cin >> s;
	cout << DP(s);
	return 0;
}
这种方法dp[i][j]只依赖于dp[i-1][j],可以用滚动数组优化成：
#include<iostream>
#include<string>
#include<vector>

using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

ll DP(const string& s)
{
	int len = s.length();
	vector<ll>dp(len);//以下标i为回文中心，j为字符下标的方案数
	vector<ll>ans(len, 0);//记录每个回文中心回文序列数
	ans[0] = 1;
	ans[len - 1] = 1;
	for (int i = 1; i < len - 1; i++)
	{
		ans[i] = 1;//对应只有自身这种情况
		ll cnt = 0;//记录上一轮dp用于累加到sum计算联合贡献
		ll sum = 0;//记录i-1下标为回文中心时的方案总数，用于联合贡献
		for (int j = len - 1; j > i; j--)
		{
			cnt = dp[j];
			if (s[j] == s[i - 1])
			{
				dp[j] += sum + 1;
				dp[j] %= MOD;
			}
			sum += cnt;
			ans[i] += dp[j];
			ans[i] %= MOD;
		}
	}
	int num = 0;
	for (int i = 0; i < len; i++)
	{
		//cout << "ans[" << i << "]: " << ans[i] << endl;
		num ^= (i + 1) * ans[i] % MOD;
	}
	return num;
}
int main(void)
{
	string s;
	cin >> s;
	cout << DP(s);
	return 0;
}