#P6835. 鱼

    ID: 6667 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTS贡献法border 链计数 DP容斥转移普通并查集回溯搜索可行性剪枝状态编码偏序集莫比乌斯反演

鱼

题目描述

把字符串 SS 的所有非空后缀插入一棵 Trie,标记每个后缀的终点。然后压缩所有既不是根、也不是后缀终点、且恰好有一个孩子的结点。压缩时,将该结点的入边和唯一出边合并为一条边。结果称为 SS 的后缀树。

给定长度 nn 和字母表大小 kk。在这 kk 种字符组成的所有 knk^n 个长度为 nn 的字符串中,求后缀树结点数的总和。每棵树的根结点也计入总和,答案对 109+710^9+7 取模。

例如字符串 bananas 的后缀树有 11 个结点。原题中的两张图展示了压缩前后的结构。

输入格式

第一行一个正整数 TT,表示询问组数。接下来 TT 行,每行两个正整数 n,kn,k。

输出格式

每组询问输出一个整数,表示结点总数对 109+710^9+7 取模的结果。

样例

3
2 2
4 3
10 2
12
447
14972

原 PDF 第三项印为 14975。逐个枚举全部 2102^{10} 个字符串并构造后缀树,复算结果为 14972。

数据范围和原赛计分

原赛有一个测试文件,覆盖 1≤k≤n≤401\le k\le n\le40 的全部 820 种不同输入。输出仍需为每组询问提供一个整数。若从 n=1n=1 到 n=Nmax⁡n=N_{\max} 的全部答案均正确,原赛计分为 ⌊2.5Nmax⁡⌋\lfloor2.5N_{\max}\rfloor。

原 PDF 和后缀树图示