你的名字
Solution
由于水平有限,笔者对于后缀自动机的应用知之甚少。
这道题作为一道经典的后缀自动机题目,对于诸如笔者的后缀自动机初学者对于后缀自动机的认识有很大帮助。
继续阅读由最短路唯一,不难发现以下性质:
1、原图可以通过对于1号点的最短路长度分层,成一棵树的形式,每一层的最短路长度相同。
2、剩下的边只能在树的同层内的点加。
3、由于要求对于i>j有dis_i>dis_j,所以每一层是一段区间。
于是,我们就可以DP了。显然有一个暴力的做法,f[i][pre_1][pre_2][now_1][now_2]表示上一层剩下的度数为1的点有pre_1个,度数为2的点有pre_2个。这一层的对应分别有now_1,now_2个。转移讨论一下i号点的连边情况。当pre_1=pre_2=0时,这一层就填完了,该填到下一层。
显然是可以通过预处理同层里的方案数直接每层转移。注意到度数为2的点的方案数要提前除2。
同时注意到,数据范围只有50,所以好写n^5暴力就可以愉快通过了。真好写