NC21587:回文子序列计数(dp)

题目链接
题意:
给一个字符串,记$X_i$表示以$i$为中心的回文串(所以串长为奇数).记$Y_i=(i+1)\ast X[i]$,求所有$Y_i$的异或和

题解:
用$f_i$记录以$i$为结尾的回文子序列(包括$i$点).然后从前往后一次计算$X_i$,关键是在这过程中如何计算.
假设已经固定了$i$点,那么让$j$从后往前跑,此时$f[j]$表示的是以$j$为结尾的回文子序列,但是并没有把$i$这个点算进去(因为此时遍历到了$i$,但还没进行更新)
那么此时的$f[j]$是不包括没有把$i$的回文子序列,一定也是$i->j$中的回文子序列,所以用$tmp$记录下这个值,然后在遇到$s[i-1]==s[j]$的时候说明$i$和$j$配对了,那么之前配对的也一定对该点也配对.更新$f[j]+=sum$
这里为什么是$sum$而不是$tmp$呢?因为$tmp$只是还没更新的单个$f[j]$的值,应当是把后面所有的还没更新的都加上去,而$sum$就是求的这个值

是不是看不太懂,那就看代码好了

#include 
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
typedef long long LL;
#define int LL
typedef pair PII;
typedef unsigned long long ULL;
inline int read(){
    int w=0,s=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') s=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
const int maxn=3005;
const int mod=1e9+7;
char s[maxn];
int f[maxn];//以i为结尾的回文子序列
int x[maxn];
void solve(){
    cin>>s;
    int n=strlen(s);
    x[0]=x[n-1]=1;
    for(int i=1;ii;j--){
            int tmp=f[j];
            if(s[j]==s[i-1]) f[j]=(f[j]+sum+1)%mod;
            sum=(sum+tmp)%mod;
            x[i]=(x[i]+f[j])%mod;
        }
    }
    int ans=0;
    for(int i=0;i