/ 
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 を出力せよ。
入力例 1
2 6 2 abbaab 5 3 abcbb
出力例 1
Yes No
1 番目のテストケースについて、例えば S' = {}ba とすると S,S' をこの順に結合して得られる文字列 abbaabba は回文になっています。また、 S',S をこの順に結合して得られる文字列 baabbaab も回文になっています。以上より S' = {}ba は条件を満たすので答えは Yes になります。
2 番目のテストケースについては、条件を満たす S' が存在しないことが証明できます。
入力例 2
3 12 400378271514996652 njvhhvjnnjvh 10 884633988115575508 rrhiyvrrur 36 71630165869626180 vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh
出力例 2
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 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