3 seconds
512 megabytes
standard input
standard output
You are given an array b1,b2,…,bn�1,�2,…,��.
An anonymous informant has told you that the array b� was obtained as follows: initially, there existed an array a1,a2,…,an�1,�2,…,��, after which the following two-component operation was performed k� times:
- A fixed point†† x� of the array a� was chosen.
- Then, the array a� was cyclically shifted to the left‡‡ exactly x� times.
As a result of k� such operations, the array b1,b2,…,bn�1,�2,…,�� was obtained. You want to check if the words of the anonymous informant can be true or if they are guaranteed to be false.
††A number x� is called a fixed point of the array a1,a2,…,an�1,�2,…,�� if 1≤x≤n1≤�≤� and ax=x��=�.
‡‡A cyclic left shift of the array a1,a2,…,an�1,�2,…,�� is the array a2,…,an,a1�2,…,��,�1.
Each test contains multiple test cases. The first line contains an integer t� (1≤t≤1041≤�≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers n,k�,� (1≤n≤2⋅1051≤�≤2⋅105, 1≤k≤1091≤�≤109) — the length of the array b� and the number of operations performed.
The second line of each test case contains n� integers b1,b2,…,bn�1,�2,…,�� (1≤bi≤1091≤��≤109) — the elements of the array b�.
It is guaranteed that the sum of the values of n� for all test cases does not exceed 2⋅1052⋅105.
For each test case, output “Yes” if the words of the anonymous informant can be true, and “No” if they are guaranteed to be false.
Yes Yes No Yes Yes No
In the first test case, the array a� could be equal to [3,2,3,4,3][3,2,3,4,3]. In the first operation, a fixed point x=2�=2 was chosen, and after 22 left shifts, the array became [3,4,3,3,2][3,4,3,3,2]. In the second operation, a fixed point x=3�=3 was chosen, and after 33 left shifts, the array became [3,2,3,4,3][3,2,3,4,3]. In the third operation, a fixed point x=3�=3 was chosen again, and after 33 left shifts, the array became [4,3,3,2,3][4,3,3,2,3], which is equal to the array b�.
In the second test case, the array a� could be equal to [7,2,1][7,2,1]. After the operation with a fixed point x=2�=2, the array became [1,7,2][1,7,2]. Then, after the operation with a fixed point x=1�=1, the array returned to its initial state [7,2,1][7,2,1]. These same 22 operations (with x=2�=2, and x=1�=1) were repeated 4949 times. So, after 100100 operations, the array returned to [7,2,1][7,2,1].
In the third test case, it can be shown that there is no solution.
SOLUTION
def can_be_true(n, k, b):
if k % n != 0:
return “No”
for i in range(n):
if b[i] == b[(i – k // n) % n]:
return “Yes”
return “No”
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
b = list(map(int, input().split()))
result = can_be_true(n, k, b)
print(result)