题目链接:
题意:给出一些数字串,每个数字串可以分成若干数字,比如123可以分成1,2,3,12,23,123。求所有数字串分成的数字的集合的和。
思路:后缀自动机:串之间用数字10隔开,建立自动机。节点p和数字j得到的子节点q,q->cnt+=p->cnt,q->sum+=p->sum*10+p->cnt*j。
const int KIND=11;struct SAM{ SAM *son[KIND],*pre; int len,sum,cnt; void init() { clr(son,NULL); pre=NULL; cnt=sum=len=0; }};SAM sam[N],*head,*last,*b[N];int d[N];int cnt,len;char s[N];void initSAM(){ sam[0].init(); head=last=&sam[0]; cnt=1;}void insert(int x){ SAM *p=&sam[cnt++],*u=last; p->init(); p->len=last->len+1; last=p; for(;u&&!u->son[x];u=u->pre) u->son[x]=p; if(!u) p->pre=head; else if(u->son[x]->len==u->len+1) p->pre=u->son[x]; else { SAM *r=&sam[cnt++],*q=u->son[x]; *r=*q; r->len=u->len+1; p->pre=q->pre=r; for(;u&&u->son[x]==q;u=u->pre) u->son[x]=r; }}void init(){ int i; FOR0(i,len+1) d[i]=0; FOR0(i,cnt) d[sam[i].len]++; FOR1(i,len) d[i]+=d[i-1]; FOR0(i,cnt) b[--d[sam[i].len]]=&sam[i];}int n;void deal(){ int ans=0,i,j; SAM *p; head->cnt=1; FOR0(i,cnt) { p=b[i]; ans=(ans+p->sum)%mod; FOR0(j,10) if(p->son[j]) { if(!i&&!j) continue; (p->son[j]->cnt+=p->cnt)%=mod; (p->son[j]->sum+=p->sum*10+p->cnt*j)%=mod; } } PR(ans);}int main(){ while(scanf("%d",&n)!=-1) { initSAM(); len=0; int i,L; while(n--) { RD(s); L=strlen(s); FOR0(i,L) insert(s[i]-'0'),len++; insert(10); len++; } init(); deal(); } return 0;}