Interesting HDU - 5785 回文树-白红宇

Interesting HDU - 5785 回文树

阅读量：5030 次

发布时间：2019-06-12

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

题意：

找出所有【i，j】为回文串【j+1，k】也为回文串的i*k乘积之和。

题解：

设sum1【i】为正着插入，到 i 的所有回文串的起始位置的前缀和，sum2【i】表示反正插入的前缀和

ans+=sum1【i]*sum1【i+1】

上面的式子很容易让我们想到两遍回文树正着和反着插入操作，

回文树的num【】表示到达 i 这个节点的回文串个数

我们用一个sum【i】数组到 i 的时候所有出现的回文串的长度的前缀和

sum1[i] = (1LL * (i + 1) * pam.num[pam.last] % mod - pam.sum[pam.last] + mod) % mod; 由于卡内存 ，所以我们就不记录sum2[]了

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" = "<
                   
                    <
                    
                     = 1; i--) {106 pam.add(s[i]);107 ans = (ans + sum1[i - 1] * (1LL * (i - 1) * pam.num[pam.last] % mod + pam.sum[pam.last]) % mod) % mod;108 }109 printf("%lld\n", ans);110 }111 return 0;112 }