https://nanti.jisuanke.com/t/30998
题意
给一串由0..9组成的数字字符串，求所有不同回文串的权值和。比如说“1121”这个串中有“1”，“2”，“11”，“121”三种回文串，他们的权值分别是1，2，11，121。最终输出ans=135。
分析
第一次知道马拉车是manacher。。。涨姿势了
在马拉车进行的过程中，进行子回文串的统计去重。
这里的哈希去重方法重点学习理解。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <ctime> #include <vector> #include <queue> #include <map> #include <stack> #include <set> #include <bitset> 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<int, int> //#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<len;i++){ Ma[l++]=s[i]; Ma[l++]='#'; } Ma[l]=0; pw[0]=p[0]=1; has[0]=sum[0]=0; for(int i=1;i<=l;i++){ p[i]=p[i-1]*base; has[i]=has[i-1]*base+Ma[i]; pw[i]=pw[i-1]*10%mod; if(Ma[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<l;i++){ if(Ma[i]!='#') ans=(ans+solve(i,i))%mod; Mp[i]=mx>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<i+Mp[i]){ mx=i+Mp[i]; id=i; } } return ans; } int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); // freopen("input.txt", "w", stdout); #endif scanf("%s",s); int len=strlen(s); printf("%lld\n",Manacher(s,len)); return 0; }
回文树的做法是先构建一颗回文树，然后dfs奇偶节点，当前节点的所代表的数字=当前添加的数字*pow(10,当前回文串长度-1) +他父亲的数字*10+当前添加的数字。
比如：33->1331 就是1*1000+33+1。此外有点卡空间，注意内存使用
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <ctime> #include <vector> #include <queue> #include <map> #include <stack> #include <set> #include <bitset> 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<int, int> //#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<len;i++) pam.add(s[i]); dfs_odd(1,0); dfs_even(0,0); printf("%lld\n",(odd+even)%mod); return 0; }