#P6835. 鱼
鱼
题目描述
把字符串 的所有非空后缀插入一棵 Trie,标记每个后缀的终点。然后压缩所有既不是根、也不是后缀终点、且恰好有一个孩子的结点。压缩时,将该结点的入边和唯一出边合并为一条边。结果称为 的后缀树。
给定长度 和字母表大小 。在这 种字符组成的所有 个长度为 的字符串中,求后缀树结点数的总和。每棵树的根结点也计入总和,答案对 取模。
例如字符串 bananas 的后缀树有 11 个结点。原题中的两张图展示了压缩前后的结构。
输入格式
第一行一个正整数 ,表示询问组数。接下来 行,每行两个正整数 。
输出格式
每组询问输出一个整数,表示结点总数对 取模的结果。
样例
3
2 2
4 3
10 2
12
447
14972
原 PDF 第三项印为 14975。逐个枚举全部 个字符串并构造后缀树,复算结果为 14972。
数据范围和原赛计分
原赛有一个测试文件,覆盖 的全部 820 种不同输入。输出仍需为每组询问提供一个整数。若从 到 的全部答案均正确,原赛计分为 。