题目描述

bzoj3238

样例

input: cacao
output: 54

解题报告

tmd我wa10次的原因是因为

ans=lens*(lens-1)*(lens+1)>>1*1LL;

改成了

ans=1LL*lens*(lens-1)*(lens+1)>>1;

就过了,,,貌似是因为我傻逼的姿势爆了LL,不管了,这道题用SAM做很简单,我们将字符串建立一棵后缀自动机,那么两个前缀的就是其在树上的的最长子串,用一个标准的我拓扑姿势求出集合的大小,然后树形dp一下就行了。

Code

发表评论

电子邮件地址不会被公开。 必填项已用*标注