HDU 4436 str2int【后缀自动机】
后缀数组也能做这题。
首先，我们先想到的是，根据数据范围，肯定是字符串的数据结构。因此想到了后缀自动机。那么后缀自动机就起到了去重的功能。
先将所有的串加上间隔符号，加入SAM，再拓扑排序。于是，对于每一个节点都可以表示多个十进制数字。
我们就可以在后缀自动机建立的图上面进行转移。
每次从父亲节点转移到儿子节点，父亲节点能够表示的所有数字都要乘以10，再加上儿子节点表示的数乘以父亲节点表示的串的个数。
sum[u] 表示每个节点能够表示的数字的和。
cnt[u] 表示每个节点能够表示的数组的个数。
// whn6325689
// Mr.Phoebe
// http://blog.csdn.net/u013007900
#include pll;
typedef complex point;
typedef pair<int, int> pii;
typedef pairint> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define getidx(l,r) (l+r | l!=r)
#define ls getidx(l,mid)
#define rs getidx(mid+1,r)
#define lson l,mid
#define rson mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=200010;
const int MAC=13;
const int MOD=2012;struct SAM
{int len[MAXN],next[MAXN][MAC],fa[MAXN];int L,last;int cnt[MAXN],num[MAXN];SAM(){init();}void init(){L=0;last=newnode(0,-1);}int newnode(int l,int pre){fa[L]=pre;cnt[L]=0,num[L]=0;for(int i=0;i1;len[L]=l;return L++;}void build(char *p){int le=strlen(p);for(int i=0;i'0');toposort();}int sum[MAXN],topo[MAXN];void toposort(){CLR(sum,0);for(int i=0; ifor(int i=1; i1];for(int i=0; ivoid add(int x){int pre=last,now=newnode(len[pre]+1,-1);last=now;while(~pre && next[pre][x]==-1){next[pre][x]=now;pre=fa[pre];}if(pre==-1) fa[now]=0;else{int bro=next[pre][x];if(len[bro]==len[pre]+1) fa[now]=bro;else{int fail=newnode(len[pre]+1,fa[bro]);for(int i=0;iwhile(~pre && next[pre][x]==bro){next[pre][x]=fail;pre=fa[pre];}}}}int solve(){cnt[0]=1;int ans=0;for(int i=0;iint u=topo[i];if(i && !cnt[u]) continue;ans=(ans+num[u])%MOD;for(int j=0;j<10;j++){if(u==0 && j==0) continue;if(next[u][j]==-1) continue;int v=next[u][j];num[v]=(num[v]+num[u]*10+cnt[u]*j)%MOD;cnt[v]+=cnt[u];}}return ans;}
}T;char str[MAXN<<1];int main()
{
//freopen("data.txt","r",stdin);int n;while(~scanf("%d",&n)){int tot=0;T.init();for(int i=1;i<=n;i++){if(tot)str[tot++]='9'+1;scanf("%s",str+tot);tot+=strlen(str+tot);}T.build(str);printf("%d\n",T.solve());}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！