A - ST and TS Palindrome

Contest Duration: 2023-01-29(Sun) 12:00 - 2023-01-29(Sun) 14:00 (local time) (120 minutes) Back to Home

A - ST and TS Palindrome Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

英小文字からなる長さ $N$ の文字列 $S$ と正整数 $K$ が与えられます。

以下の条件を満たす長さ $K$ の文字列 $S'$ が存在するか判定してください。

$S, S'$ をこの順に結合して得られる文字列は回文である
$S', S$ をこの順に結合して得られる文字列は回文である

$T$ 個のテストケースが与えられるのでそれぞれについて判定してください。

制約

$1 \leq T \leq 10^5$
$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq 10^{18}$
$S$ は英小文字からなる長さ $N$ の文字列
入力される数値はすべて整数
$1$ つの入力に含まれるテストケースについて、 $N$ の総和は $2 \times 10^5$ 以下

入力

入力は以下の形式で標準入力から与えられます。

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

各ケースは以下の形式で与えられます。

 $N$   $K$ 
 $S$

出力

$T$ 行出力せよ。 $i$ 行目には $i$ 番目のテストケースについて、条件を満たす文字列 $S'$ が存在する場合は Yes を、存在しない場合は No を出力せよ。

入力例 1Copy

Copy

2
6 2
abbaab
5 3
abcbb

出力例 1Copy

Copy

Yes
No

$1$ 番目のテストケースについて、例えば $S' = {}$ ba とすると $S,S'$ をこの順に結合して得られる文字列 abbaabba は回文になっています。また、 $S',S$ をこの順に結合して得られる文字列 baabbaab も回文になっています。以上より $S' = {}$ ba は条件を満たすので答えは Yes になります。

$2$ 番目のテストケースについては、条件を満たす $S'$ が存在しないことが証明できます。

入力例 2Copy

Copy

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

出力例 2Copy

Copy

Yes
No
Yes

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 1Copy

Copy

2
6 2
abbaab
5 3
abcbb

Sample Output 1Copy

Copy

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 2Copy

Copy

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

Sample Output 2Copy

Copy

Yes
No
Yes