分数: 1100 点
问题陈述
我们将通过连接两个相等的字符串获得的字符串称为 甚至 字符串。
例如, xyzxyz 和 aaaaaa 是偶数,而 ababab 和 xyzxy 不是。
对于非空字符串 S,我们将定义 f(S) 作为最短的偶数字符串,可以通过在末尾附加一个或多个字符来获得 S。
例如, f(abaaba)=abaababaab。
可以证明 f(S) 是唯一确定的非空字符串 S.
给你一个偶数字符串 S 由小写英文字母组成。 对于小写英文字母表中的每个字母,找出它出现的次数 l- 第一个字符 r- 第一个字符 f^{10^{100}} (S).
在这里, f^{10^{100}} (S) 是字符串 f(f(f( ... f(S) ... ))) 通过申请获得 f to S 10^{100} 次。
约束
- 2 \leq |S| \leq 2\times 10^5
- 1 \leq l \leq r \leq 10^{18}
- S 是由小写英文字母组成的偶数字符串。
- l 和 r 是整数。
输入
输入由标准输入按以下格式给出:
S l r
输出
打印 26 整数位于一行中,中间有空格。 的 i- 第一个整数应该是出现的次数 i- 小写英文字母表中的第一个字母 l- 第一个字符 r- 第一个字符 f^{10^{100}} (S).
示例输入 1
abaaba 6 10
示例输出 1
3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
自从 f(abaaba)=abaababaab,前十个字符 f^{10^{100}}(S) 也是 abaababaab。因此,第六到第十个字符是 abaab。在这个字符串中, a 出现三次, b 出现两次并且没有其他字母出现,因此输出应该是 3 和 2 后面跟着二十四 0s。
示例输入 2
xx 1 1000000000000000000
示例输出 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000000000000 0 0
示例输入 3
vgxgpuamkvgxgvgxgpuamkvgxg 1 1000000000000000000
示例输出 3
87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0