← 返回题目列表

Codeforces · 1411/E

E. 波曼号码

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

你从你的朋友那里得到了一个由$$$n$$$小写英文字母组成的字符串$$$S$$$。原来,这是一个用波曼数字写的数字。波曼数字系统早已被遗忘。剩下的就是将数字从波曼数字转换为我们熟悉的数字系统的算法。 $$$S$$$ 的字符从左到右从 $$$1$$$ 到 $$$n$$$ 编号。我们将$$$S$$$的值表示为$$$f(S)$$$,其定义如下:

- 如果 $$$|S| > 1$$$,选择任意整数$$$m$$$ ($$$1 \le m < |S|$$$),定义$$$f(S) = -f(S[1, m]) + f(S[m + 1, |S|])$$$,其中$$$S[l, r]$$$表示$$$S$$$从第$$$l$$$到第$$$S$$$的子串第 $$$r$$$ 个位置(包含在内)。
- 否则 $$$S = c$$$,其中 $$$c$$$ 是一些英文字母。那么 $$$f(S) = 2^{pos(c)}$$$,其中 $$$pos(c)$$$ 是字母 $$$c$$$ 在字母表中的位置 ($$$pos($$$a$$$) = 0$$$, $$$pos($$$z$$$) = 25$$$)。

请注意,$$$m$$$ 在每个步骤中都是独立选择的。

你的朋友认为通过在每一步选择正确的 $$$m$$$ 可以得到 $$$f(S) = T$$$。他说得对吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$T$$$ ($$$2 \leq n \leq 10^5$$$, $$$-10^{15} \leq T \leq 10^{15}$$$)。

第二行包含$$$S$$$由$$$n$$$小写英文字母组成的字符串。

输出

如果可以获得所需的值,请打印“是”。否则,打印“否”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

2 -1
ba

输出 #1

Yes

输入 #2

3 -7
abc

输出 #2

No

输入 #3

7 -475391
qohshra

输出 #3

Yes

注意

在第二个示例中,您无法获得 $$$-7$$$。但你可以得到$$$1$$$,例如,如下:

1. 首先选择 $$$m = 1$$$,然后选择 $$$f($$$abc$$$) = -f($$$a$$$) + f($$$bc$$$)$$$
2. $$$f($$$a$$$) = 2^0 = 1$$$
3. $$$f($$$bc$$$) = -f($$$b$$$) + f($$$c$$$) = -2^1 + 2^2 = 2$$$
4.最后$$$f($$$abc$$$) = -1 + 2 = 1$$$