CF1411E.Poman Numbers

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You've got a string SS consisting of nn lowercase English letters from your friend. It turned out that this is a number written in poman numerals. The poman numeral system is long forgotten. All that's left is the algorithm to transform number from poman numerals to the numeral system familiar to us. Characters of SS are numbered from 11 to nn from left to right. Let's denote the value of SS as f(S)f(S), it is defined as follows:

  • If ∣S∣>1|S| \gt 1, an arbitrary integer mm (1≤m<∣S∣1 \le m \lt |S|) is chosen, and it is defined that f(S)=−f(S[1,m])+f(S[m+1,∣S∣])f(S) = -f(S[1, m]) + f(S[m + 1, |S|]), where S[l,r]S[l, r] denotes the substring of SS from the ll-th to the rr-th position, inclusively.
  • Otherwise S=cS = c, where cc is some English letter. Then f(S)=2pos(c)f(S) = 2^{pos(c)}, where pos(c)pos(c) is the position of letter cc in the alphabet (pos(pos(a)=0) = 0, pos(pos(z)=25) = 25).

Note that mm is chosen independently on each step.

Your friend thinks it is possible to get f(S)=Tf(S) = T by choosing the right mm on every step. Is he right?

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

  • 若 ∣S∣>1|S| \gt 1,则任选一个整数 mm(满足 1≤m<∣S∣1 \le m \lt |S|),并定义 f(S)=−f(S[1,m])+f(S[m+1,∣S∣])f(S) = -f(S[1, m]) + f(S[m + 1, |S|]),其中 S[l,r]S[l, r] 表示 SS 中从第 ll 个位置到第 rr 个位置(含端点)的子串;
  • 否则 S=cS = c,其中 cc 是某个英文字母,此时 f(S)=2pos(c)f(S) = 2^{pos(c)},而 pos(c)pos(c) 表示字母 cc 在英文字母表中的位置(即 pos(pos(a)=0) = 0,pos(pos(z)=25) = 25)。

注意:每一步中 mm 的选取是相互独立的。

你的朋友认为,只要在每一步都恰当地选择 mm,就一定能使得 f(S)=Tf(S) = T。他的说法正确吗?

输入格式

The first line contains two integers nn and TT (2≤n≤1052 \leq n \leq 10^5, −1015≤T≤1015-10^{15} \leq T \leq 10^{15}).

The second line contains a string SS consisting of nn lowercase English letters.

第一行包含两个整数 nn 和 TT(2≤n≤1052 \leq n \leq 10^5,−1015≤T≤1015-10^{15} \leq T \leq 10^{15})。

第二行包含一个由 nn 个小写英文字母组成的字符串 SS。

输出格式

Print "Yes" if it is possible to get the desired value. Otherwise, print "No".

You can print each letter in any case (upper or lower).

如果可以得到目标值,则输出“Yes”;否则输出“No”。

您可以以任意大小写(大写或小写)输出每个字母。

输入输出样例

  • 输入#1

    2 -1
    ba

    输出#1

    Yes
  • 输入#2

    3 -7
    abc

    输出#2

    No
  • 输入#3

    7 -475391
    qohshra

    输出#3

    Yes

说明/提示

In the second example, you cannot get −7-7. But you can get 11, for example, as follows:

  1. First choose m=1m = 1, then f(f(abc)=−f() = -f(a)+f() + f(bc))
  2. f(f(a)=20=1) = 2^0 = 1
  3. f(f(bc)=−f() = -f(b)+f() + f(c)=−21+22=2) = -2^1 + 2^2 = 2
  4. In the end f(f(abc)=−1+2=1) = -1 + 2 = 1

在第二个例子中,你无法得到 −7-7。但你可以得到 11,例如,按如下步骤进行:

  1. 首先选择 m=1m = 1,则 f(f(abc)=−f() = -f(a)+f() + f(bc))
  2. f(f(a)=20=1) = 2^0 = 1
  3. f(f(bc)=−f() = -f(b)+f() + f(c)=−21+22=2) = -2^1 + 2^2 = 2
  4. 最终 f(f(abc)=−1+2=1) = -1 + 2 = 1

输入解题思路,AI测评打分。不知道怎么写?

首页