【AHOI2013】差异


题意

求 \(\sum_{1\le i < j \le n} len(T_i)+len(T_j)-2\times lcp(t_i,t_j)\) 。

题解

\(\sum_{1\le i < j \le n} len(T_i)+len(T_j)-2\times lcp(t_i,t_j)\)

\(=\sum_{1\le i < j \le n} len(T_i)+len(T_j)-\sum_{1\le i < j \le n} 2\times lcp(t_i,t_j)\)。

\(\sum_{1\le i < j \le n} len(T_i)+len(T_j)\)

\(=\sum_{1\le i < j \le n} (n-i+1)+(n-j+1)\)。

这部分直接暴力等差数列结算即可。

对于另一部分 \(\sum_{1\le i < j \le n} 2\times lcp(t_i,t_j)\) ,显然,两个后缀的 lcp 就是他们 sam 上的最近公共 \(link\) ,一个状态如果包含一个后缀的话,那么这个状态一定是一开始的未被拆点前的状态,而且这个后缀的长度就是这个状态的 \(len\) ,于是我们根据 \(link\) 建出树,在树上计算每个状态的贡献即可。

分两类情况:

  • 一个状态的贡献是不同孩子里面选取两个方案数 * \(len\);
  • 自己状态是一个后缀,再从孩子里选取一个,即孩子的数量 * \(len\) 。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 2,011

Categories

Archive