SRM708 div1 PalindromicSubseq（动态规划+容斥原理）-白红宇

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

阅读量：6818 次

发布时间：2019-06-26

本文共 1737 字，大约阅读时间需要 5 分钟。

题目大意：给定一个字符串，记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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;typedef long long LL;const int maxn = 3050;const int MOD = 1e9 + 7;LL F[maxn][maxn], G[maxn][maxn];string S;LL g(int l, int r){ if(l < 0 || r >= S.length()) return 1; if(G[l][r]) return G[l][r]; G[l][r] = ((LL)g(l-1, r) + g(l, r+1) - (S[l] == S[r] ? 0 : g(l-1, r+1)))%MOD; return G[l][r];}LL f(int l, int r){ if(l > r) return 1; if(l == r) return 2; if(F[l][r]) return F[l][r]; F[l][r] = ((LL)f(l+1, r) + f(l, r-1) - (S[l] == S[r] ? 0 : f(l+1, r-1)))%MOD; return F[l][r];}class PalindromicSubseq { public: int solve(string s) { memset(F, 0, sizeof(F)); memset(G, 0, sizeof(G)); S = s; LL ans = 0; for(int i = 0; i < s.length(); i++){ LL temp = 0; for(int j = 0; j < s.length(); j++) if(s[i] == s[j]){ int l = min(i, j), r = max(i, j); (temp += (LL)f(l+1, r-1)*g(l-1, r+1)%MOD) %= MOD; } (temp += MOD) %= MOD; (temp *= (LL)(i+1)) %= MOD; ans ^= temp; } return ans; }};