201550: [AtCoder]ARC155 A - ST and TS Palindrome

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters, and a positive integer $K$.

Determine whether there is a string $S'$ of length $K$ that satisfies the following conditions.

  • The concatenation of $S$ and $S'$ in this order is a palindrome.
  • The concatenation of $S'$ and $S$ in this order is a palindrome.

You have $T$ test cases to solve.

Constraints

  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 10^{18}$
  • $S$ is a string of length $N$ consisting of lowercase English letters.
  • All numbers in the input are integers.
  • In each input file, the sum of $N$ over the test cases is at most $2 \times 10^5$.

Input

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

Each case is in the following format:

$N$ $K$
$S$

Output

Print $T$ lines. The $i$-th line should contain Yes if there is a string $S'$ that satisfies the conditions for the $i$-th test case, and No otherwise.


Sample Input 1

2
6 2
abbaab
5 3
abcbb

Sample Output 1

Yes
No

For the first test case, if we let $S' = {}$ba, for instance, the concatenation of $S$ and $S'$ in this order will be abbaabba, which is a palindrome. Here, the concatenation of $S'$ and $S$ in this order is baabbaab, which is also a palindrome. Thus, $S' = {}$ba satisfies the condition, so the answer is Yes.

For the second test case, we can prove that no string satisfies the conditions.


Sample Input 2

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

Sample Output 2

Yes
No
Yes

Input

题意翻译

$T$ 组数据。 每组给定 $N$,$K$ 和长度为 $N$ 的字符串 $S$,求是否能构造一个长度为 $K$ 的字符串 $V$,使得 $VS$ 和$SV$ 都为回文串。

加入题单

上一题 下一题 算法标签: