回文子序列计数（dp）

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

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
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

输入

复制

axbcba

输出

复制

31

示例2

输入

复制

eeeee

输出

复制

14

示例3

输入

复制

zyzyzzzzxzyz

输出

复制

221

示例4

输入

复制

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

输出

复制

1044407608

备注:

子任务1：n<=100

子任务2：n<=500

子任务3：n<=3000

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=3e3+5;
const int mod=1e9+7;
ll X[N],dp[N];//dp[i]代表以i为结尾的回文子序列数目（从右往左看)） 
char s[N];
int main(){
    scanf("%s",s);
    int len=strlen(s);
    X[0]=1;
    X[len-1]=1;
    for(int i=1;i<len-1;i++){
    	X[i]=1;
    	ll sum=0,cnt=0; 
    	for(int j=len-1;j>i;j--){
    		cnt=dp[j];
    		if(s[j]==s[i-1]){
    			dp[j]=(dp[j]+sum+1)%mod;
			}
			sum=(sum+cnt)%mod;
			X[i]=(X[i]+dp[j])%mod;
		}
	}
	ll ans=0;
	for(int i=0;i<len;i++) ans=ans^(((i+1)*X[i])%mod);
	printf("%lld\n",ans);
	return 0;
}