Harry and magic string HDU - 5157 记录不相交的回文串对数-白红宇

Harry and magic string HDU - 5157 记录不相交的回文串对数

阅读量：5030 次

发布时间：2019-06-12

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

题意：

记录不相交的回文串对数

题解：

正着反着都来一遍回文树

用sum1【i】表示到 i 位置，出现的回文串个数的前缀和

sun2【i】表示反着的个数

ans+=sum1【i-1】*sum2【i】

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <
                    
                     = 0; --i)cnt[fail[i]] += cnt[i]; 95 //逆序累加，保证每个点都会比它的父亲节点先算完，于是父亲节点能加到所有子孙 96 } 97 } pam; 98 99 int main() {100 // FIN;101 while (~sfs(s + 1)) {102 pam.init();103 int n = strlen(s + 1);104 for (int i = 1; i <= n; i++) {105 pam.add(s[i], i);106 sum[i] = sum[i - 1] + pam.num[pam.last];107 }108 pam.init();109 LL ans = 0;110 for (int i = n; i >= 1; --i) {111 pam.add(s[i], i);112 ans += pam.num[pam.last] * sum[i - 1];113 }114 printf("%lld\n", ans);115 }116 return 0;117 }