← 返回题目列表

AtCoder · arc077_d

F. 不锈钢

中文机器翻译题面 查看原题

分数: 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