#P4175. [2015年湖南省队省队集训]小G的电话本

    ID: 3393 传统题 1000ms 512MiB 尝试: 365 已通过: 50 难度: 8 上传者: 标签>难度分类提高+/省选-字符串后缀自动机endpos 等价类按长度传播出现次数多项式与生成函数普通生成函数生成函数求系数NTT数论快速幂截断幂级数CF2500

[2015年湖南省队省队集训]小G的电话本

[2015 湖南省队集训] 小 G 的电话本

题目描述

小 G 的电话本里有一个名字 SS,托尼想统计它的片段。一个片段是从 SS 中选出的一个非空连续子串,由它的起止位置唯一确定。内容相同但位于不同位置的片段是不同的片段。

对于一个片段 PP,记 c(P)c(P) 为它的内容在 SS 中出现的次数。每个不同的出现位置都计入,包括相互重叠的出现。

求满足 ∑i=1kc(Pi)=m\sum_{i=1}^{k}c(P_i)=m 的有序 kk 元组 (P1,P2,…,Pk)(P_1,P_2,\ldots,P_k) 的数量。同一片段可以在一个元组中选多次;只要某一项选取的片段位置不同,两个元组就不同。

输入格式

第一行两个整数 k,mk,m。第二行给出名字 SS。令 nn 为 SS 的长度,满足 1≤n,k≤1051\le n,k\le10^5,1≤m≤n1\le m\le n。

输出格式

输出一行一个整数,表示方案数对 10050600971005060097 的非负余数。

样例 #1

样例输入 #1

3 4
aaaaa

样例输出 #1

6

样例说明

字符串有两处内容为 aaaa\texttt{aaaa} 的片段,分别从第 11、22 个位置开始;它们的出现次数都是 22。完整字符串 aaaaa\texttt{aaaaa} 的出现次数是 11。任意选择这两处短片段之一放入元组的任一项,另外两项都选完整字符串。答案为 2×3=62\times3=6。