SRM708 div1 PalindromicSubseq（动态规划+容斥原理）

题目大意：给定一个字符串，记X[i]为包含s[i]这个字符的所有子列是回文串的个数（注意是子列而不是子串），求出所有的X[i]*(i+1)，然后异或起来作为返回结果

题解：

首先用容斥来想，如果当前枚举到i

那么答案就是

1、选i作为中间的字幕，(0, i-1)和(i+1, L)这两个区间相互匹配回文

2、直接选(0, i)，(i+1, L)这两个区间相互匹配回文

3、直接选(0, i-1), (i, L)这两个区间相互回文匹配

然后我们发现后两种情况会有重叠情况

我们把这两种情况更细致的分一下，(0, i), (i+1,L)如果能匹配，那么必定要找到s[j] = s[i], j是属于(i+1, L)的

然后我们这样来做

令f[l][r]表示，只用(l, r)区间就可以构成回文串的个数

令g[l][r]表示，用(0, l), (r, L)2个区间相互回文匹配构成的个数

然后没找到一对(i, j)，乘一下f[i+1][j-1], g[i-1][j+1]即可

转移：

f[l][r] = f[l+1][r] + f[l][r-1] - (s[l] == s[r] ? 0 : f[l+1][r-1])

g[l][r] = g[l-1][r] + g[l][r+1] - (s[l] == s[r] ? 0 : s[l-1][r+1])

然后就可以做了

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <typeinfo>

#include <fstream>

using namespace std;

typedef long long LL;

const int maxn = ;

const int MOD = 1e9 + ;

LL F[maxn][maxn], G[maxn][maxn];

string S;

LL g(int l, int r){

    if(l <  || r >= S.length()) return ;

    if(G[l][r]) return G[l][r];

    G[l][r] = ((LL)g(l-, r) + g(l, r+) - (S[l] == S[r] ?  : g(l-, r+)))%MOD;

    return G[l][r];

}

LL f(int l, int r){

    if(l > r) return ;

    if(l == r) return ;

    if(F[l][r]) return F[l][r];

    F[l][r] = ((LL)f(l+, r) + f(l, r-) - (S[l] == S[r] ?  : f(l+, r-)))%MOD;

    return F[l][r];

}

class PalindromicSubseq {

    public:

    int solve(string s) {

        memset(F, , sizeof(F));

        memset(G, , sizeof(G));

        S = s;

        LL ans = ;

        for(int i = ; i < s.length(); i++){

            LL temp = ;

            for(int j = ; j < s.length(); j++)

            if(s[i] == s[j]){

               int l = min(i, j), r = max(i, j);

               (temp += (LL)f(l+, r-)*g(l-, r+)%MOD) %= MOD;

            }

            (temp += MOD) %= MOD;

            (temp *= (LL)(i+)) %= MOD;

            ans ^= temp;

        }

        return ans;

    }

};

巴特西

SRM708 div1 PalindromicSubseq（动态规划+容斥原理）

最新文章

热门文章