链接：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

思路和心得：

（一）二维dp

1.需要dp，求两个端点的，左右两端的，能形成回文子序列的数量
2.枚举mid，作为奇回文子序列的中心
也可以看做是枚举l，每次只计算以为中心的情形
3.由于dp递推关系式，决定了r的遍历顺序是从右往左
4.每当。对于这个来说。我可以配合右侧所有的情形，也可以不和右侧的配合 就
5.而，是r指针从右往左的 的情况数
是方便计算用的
6.对于来说。它作为中心点的回文子序列情形，是把 这个区间作为右端点的情形都 加一遍。

7.python3 TLE 我也还没想到好的办法

python3代码

MOD = 10 ** 9 + 7

s = input()
n = len(s)

x = [1 for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]

for l in range(0, n - 1):
    mid = l + 1
    right_acc = 0
    for r in range(n - 1, mid, -1):
        dp[l][r] = dp[l - 1][r] if 0 <= l - 1 else 0
        if s[l] == s[r]:
            dp[l][r] = (dp[l][r] + right_acc + 1) % MOD

        right_acc = (right_acc + dp[l - 1][r] if 0 <= l - 1 else 0) % MOD

    for r in range(n - 1, mid, -1):
        x[mid] = (x[mid] + dp[l][r]) % MOD

# print(x)
res = 0
for i in range(n):
    res ^= ((i + 1) * x[i]) % MOD
print(res)

c++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    string s;    cin >> s;
    int n = s.size();
    long long x[n];
    for (int i = 0; i < n; i ++)
        x[i] = 1;
    long long dp[n][n];
    memset(dp, 0, sizeof(dp));

    for (int l = 0; l < n - 1; l ++)
    {
        int mid = l + 1;
        long long right_acc = 0;
        for (int r = n - 1; r > mid; r --)
        {
            dp[l][r] = (0 <= l - 1 ? dp[l - 1][r] : 0);
            if (s[mid - 1] == s[r])
                dp[l][r] = (dp[l][r] + right_acc + 1) % MOD;

            right_acc = (right_acc + (0 <= l - 1 ? dp[l - 1][r] : 0)) % MOD;
        }

        for (int r = n - 1; r > mid; r --)
        {
            x[mid] = (x[mid] + dp[l][r]) % MOD;
        }
    }

    long long res = 0;
    for (int i = 0; i < n; i ++)
    {
        res ^= ((i + 1) * x[i]) % MOD;
    }
    cout << res << endl;

    return 0;
}

java代码

import java.util.* ;

public class Main
{
    public static void main(String [] args)
    {
        long MOD = (long)(1e9 + 7);
        Scanner scan = new Scanner(System.in);

        String s = scan.next();
        int n = s.length();

        long [] x = new long [n];
        Arrays.fill(x, 1);
        long [][] dp = new long [n][n];

        for (int l = 0; l < n - 1; l ++)
        {
            int mid = l + 1;
            long right_acc = 0;
            for (int r = n - 1; r > mid; r --)
            {
                dp[l][r] = (0 <= l - 1 ? dp[l - 1][r] : 0);
                long old = dp[l][r];
                if (s.charAt(l) == s.charAt(r))
                    dp[l][r] = (dp[l][r] + right_acc + 1) % MOD;

                right_acc = (right_acc + (0 <= l - 1 ? dp[l - 1][r] : 0)) % MOD;
            }

            for (int r = n - 1; r > mid; r --)
               x[mid] = (x[mid] + dp[l][r]) % MOD;
        }

        long res = 0;
        for (int i = 0; i < n; i ++)
        {
            res ^= ((i + 1) * x[i]) % MOD;
        }
        System.out.println(res);
    }
}