ACM-ICPC 2018 南京赛区网络预赛 I Skr (马拉车+hash去重)或(回文树)-白红宇

ACM-ICPC 2018 南京赛区网络预赛 I Skr (马拉车+hash去重)或(回文树)

阅读量：6474 次

发布时间：2019-06-23

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

题意

给一串由0..9组成的数字字符串，求所有不同回文串的权值和。比如说“1121”这个串中有“1”，“2”，“11”，“121”三种回文串，他们的权值分别是1，2，11，121。最终输出ans=135。

分析

第一次知道马拉车是manacher。。。涨姿势了

在马拉车进行的过程中，进行子回文串的统计去重。

这里的哈希去重方法重点学习理解。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(a, b) memset(a, b, sizeof(a))#define pb push_back#define mp make_pair#define pii pair
                   
                    //#define eps 0.0000000001#define IOS ios::sync_with_stdio(0);cin.tie(0);#define random(a, b) rand()*rand()%(b-a+1)+a#define pi acos(-1)//const ll INF = 0x3f3f3f3f3f3f3f3fll;const int inf = 0x3f3f3f3f;const int maxn = 2e6 + 10;const int maxm = 3000000 +10;const int mod = 1000000007;ull base=10007;ull p[maxn<<1],has[maxn<<1];ll pw[maxn<<1],sum[maxn<<1];const int MOD=400007;int head[maxn<<1],nxt[maxn<<1],cnt=0;ull val[maxn];bool exist(ull now){ int u=now%MOD; for(int i=head[u];i;i=nxt[i]){ if(val[i]==now) return true; } val[cnt]=now; nxt[cnt]=head[u]; head[u]=cnt++; return false;}ull gethas(int l,int r){ return has[r]-has[l-1]*p[r-l+1];}ll solve(int l,int r){ ull tmp=gethas(l,r); if(exist(tmp)) return 0; ll ans=(sum[r]-sum[l-1]*pw[(r-l+1+1)/2]%mod+mod)%mod; return ans;}char s[maxn];char Ma[maxn<<1];int Mp[maxn<<1];ll Manacher(char s[],int len){ int l=0; Ma[l++]='$'; Ma[l++]='#'; for(int i=0;i
                    
                     ='0'&&Ma[i]<='9'){ sum[i]=(sum[i-1]*10+Ma[i]-'0')%mod; }else{ sum[i]=sum[i-1]; } } ll ans=0; int mx=0,id=0; for(int i=0;i
                     
                      i?min(Mp[2*id-i],mx-i):1; while(Ma[i+Mp[i]]==Ma[i-Mp[i]]){ if(Ma[i+Mp[i]]!='#') ans=(ans+solve(i-Mp[i],i+Mp[i]))%mod; Mp[i]++; } if(mx

回文树的做法是先构建一颗回文树，然后dfs奇偶节点，当前节点的所代表的数字=当前添加的数字*pow(10,当前回文串长度-1) +他父亲的数字*10+当前添加的数字。

比如：33->1331 就是1*1000+33+1。此外有点卡空间，注意内存使用

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(a, b) memset(a, b, sizeof(a))#define pb push_back#define mp make_pair#define pii pair
                   
                    //#define eps 0.0000000001#define IOS ios::sync_with_stdio(0);cin.tie(0);#define random(a, b) rand()*rand()%(b-a+1)+a#define pi acos(-1)//const ll INF = 0x3f3f3f3f3f3f3f3fll;const int inf = 0x3f3f3f3f;const int maxn = 2e6 + 10;const int maxm = 3000000 +10;const int mod = 1e9+7;struct PAM{ int nxt[maxn][10]; int fail[maxn]; int cnt[maxn]; int num[maxn]; int len[maxn]; int s[maxn]; int last,n,p; int newnode(int w){ for(int i=0;i<26;i++) nxt[p][i]=0; num[p]=cnt[p]=0; len[p]=w; return p++; } void init(){ n=last=p=0; newnode(0); newnode(-1); s[n]=-1; fail[0]=1; } int get_fail(int x){ while(s[n-len[x]-1]!=s[n]) x=fail[x]; return x; } void add(int c){ c-='0'; s[++n]=c; int cur=get_fail(last); if(!nxt[cur][c]){ int now=newnode(len[cur]+2); fail[now]=nxt[get_fail(fail[cur])][c]; nxt[cur][c]=now; num[now]=num[fail[now]]+1; } last=nxt[cur][c]; cnt[last]++; } void Count(){ for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i]; }};PAM pam;char s[maxn];ll odd=0;ll even=0;ll qpow(ll a,ll b){ ll res=1; while(b){ if(b&1) res=a*res%mod; b>>=1; a=a*a%mod; } return res;}void dfs_odd(int x,ll fa){ for(int i=1;i<=9;i++){ if(pam.nxt[x][i]){ ll cur; if(pam.len[pam.nxt[x][i]]==1){ odd=(i+odd)%mod; cur=i; }else{ cur=(i*qpow(10,pam.len[pam.nxt[x][i]]-1)%mod+i+fa*10%mod)%mod; odd=(odd+cur%mod)%mod; } dfs_odd(pam.nxt[x][i],cur); } }}void dfs_even(int x,ll fa){ for(int i=1;i<=9;i++){ if(pam.nxt[x][i]){ ll cur=(i*qpow(10,pam.len[pam.nxt[x][i]]-1)%mod+i+fa*10%mod)%mod; even=(even+cur)%mod; dfs_even(pam.nxt[x][i],cur); } }}int main() {#ifdef LOCAL freopen("in.txt", "r", stdin);// freopen("input.txt", "w", stdout);#endif pam.init(); scanf("%s",s); int len=strlen(s); for(int i=0;i

转载于:https://www.cnblogs.com/fht-litost/p/9593930.html

你可能感兴趣的文章