#P9490. 最良表現

    ID: 6060 传统题 1000ms 256MiB 尝试: 107 已通过: 18 难度: 7 上传者: 标签>CF2300提高+/省选-KMP周期判定前后缀分解暴力枚举900

最良表現

题面翻译

设xx是一个长度至少为1的字符串,我们称xx是好的,当且仅当对于任意字符串yy和任意整数k(k≥2)k(k≥2),由yy复制kk次并连接得到的字符串均与xx不同。 举个例子,a,bbc和cdcdc是好串,然而aa,bbbb和cdcdcd不是。

设ww是一个长度至少为1的字符串,对于一个由mm个元素组成的序列 F=(f1,f2,...,fm)F=(f_1,f_2,...,f_m),我们称FF为ww的一个“亮眼表现”当且仅当下面的条件同时被满足:

  • 对于任意i(1≤i≤m)i(1≤i≤m),元素fif_i是一个好串。
  • 把f1,f2,...,fmf_1,f_2,...,f_m按顺序连接起来得到的字符串就是ww。

举个例子,当ww='aabb'时,ww有五个亮眼表现:

  • (aabb)
  • (a,abb)
  • (aab,b)
  • (a,ab,b)
  • (a,a,b,b)

在ww的所有亮眼表现中,元素数量最少的那个(些)亮眼表现被称为ww的“全场最佳”。举个例子,当ww='aabb'时,ww的全场最佳只有一个:(aabb)。

给你一个字符串ww,请计算:

  • ww的一个全场最佳所含的元素数量
  • ww有多少个全场最佳(对1e9+7取模)

(数据保证ww一定存在亮眼表现)

样例 #1

样例输入 #1

aab

样例输出 #1

1
1

样例 #2

样例输入 #2

bcbc

样例输出 #2

2
3

样例 #3

样例输入 #3

ddd

样例输出 #3

3
1

提示

制約

  • $1\ \leq\ |w|\ \leq\ 500000\ \,\ (=5\ \times\ 10^5)$

输入均为小写字母